[Greedy] 멀티탭 스케줄링 - 백준

https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

 

본 문제를 푼 관점은 다음과 같이 풀어보았습니다.

 

처음에는 단순 완전 탐색 문제라고 생각을 했습니다. 

 

예를 들어보면

 

다음과 같은 예제가 있다고 하면

현재는 2, 1, 3 제품에 대한 멀티탭을 꽂은 상황입니다. 

여기서 예를 들어 다음으로 4를 꽂아야 할 차례인데 4는 현재 멀티탭을 꽂을 곳이 없습니다. 따라서 코드를 빼야하는 상황이 생기는데 이 코드를 빼는 횟수를 최소화를 해야합니다. 

 

그래서, 처음으로는 단순하게 현재 2,1,3에서 앞으로 가장 등장횟수가 적은 얘, 예를 들어 이 문제에서는 2, 1, 3 셋다 한 번씩만 등장하므로 아무거나 빼도 된다고 생각해서 2를 뽑았습니다.

 

즉, 

다음에서 4를 대체할 때 4를 포함한 남은 리스트에서 

현재 꽂혀 있는 애들 중 가장 등장 횟수가 적은 애를 교체하는 것입니다. 

다음과 같이 구성한 코드는 다음과 같습니다. 

 

### Brute Force로 풀기, 22%에서 실패
from collections import Counter
n, k = [int(x) for x in input().split()]
num_list = [int(x) for x in input().split()]

current = []

i = 0

while True :
    if len(current) == n :
        break
    if num_list[i] not in current :
        current.append(num_list[i])
    i += 1

def find(before,after,target) :
    dics = Counter(after)
    mins = float('inf'); answer = 0;
    for b in before :
        if mins > dics[b] :
            mins = dics[b]
            answer = b
    before[before.index(answer)] = target
    return before
    
cnt = 0
while True :
    if i == len(num_list) :
        break
    target = num_list[i]
    if target not in current :
        current = find(current, num_list[i:], target)
        cnt += 1
    i += 1

print(cnt)

하지만 22%에서 실패가 떠가지고 어떤 것이 문제인지를 살펴보았습니다.

 

여기서 최적이 꼭 카운트로 계산이 될까? 라는 의문이 들었고

혹시 유사한 반례가 있나 찾아보니

 

다음과 같은 반례를 풀지 못하였습니다. 

2 15
3 2 1 2 1 2 1 2 1 3 3 3 3 3 3

 

이 경우 실제 정답은 2가 나오지만 제 알고리즘에서는 7이 나왔습니다.

즉 제 알고리즘이 최적을 보장하지 못하였습니다.

 

그래서 생각을 바꾸어보았습니다.

 

현재 꽂혀 있는 플러그에서 가장 나중에 등장하는 애를 바꾸는 것이 최적일 것이라는 생각이 들었습니다. 

 

예를 들면 위 예제를 다시 보면

다음 교체 대상 4를 기준으로 2, 1, 3의 거리를 계산하면

1이 가장 먼 것을 확인할 수 있습니다.

따라서 1을 교체하는 것으로 문제를 바꾸었더니

다행히 통과를 할 수 있었습니다.

구현 코드는 다음과 같습니다. 

 

n, k = [int(x) for x in input().split()]
num_list = [int(x) for x in input().split()]

## 현재 것을 만들어놓기
current = []
i = 0

while True :
    if len(current) == n :
        break
    if num_list[i] not in current :
        current.append(num_list[i])
    i += 1

def find(before, after, target) :
    maxs= 0
    for b in before :
        try :
            k = after.index(b)
            if maxs < k :
                maxs = k
                answer = b
        except :
            answer = b
            break
    before[before.index(answer)] = target
    return before

cnt =0
while True :
    if i == len(num_list) : break
    target = num_list[i]
    if target not in current :
        current = find(current, num_list[i:], target)
        cnt += 1
    i += 1

print(cnt)