[알로리즘] 백준 1700 멀티탭 스케줄링

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

처음 문제만 보고는 쉽다고 생각했었다. 처음 내가 생각한 풀이는 다음과 같았다.

• 각 물건 번호를 key로하고, 해당 물건이 사용되는 횟수를 value로 하는 dictionary를 하나 선언한다.

• 이미 멀티탭에 같은 물건이 꽂혀 있을 경우, continue로 생략

  • dictionary에서 해당 물건의 갯수(value) -1

• 같은 물건이 꽂혀 있지 않고, 멀티탭 공간에 여유가 있는 경우

  • dictionary에서 해당 물건의 갯수(value) -1
  • 멀티탭 리스트에 해당 물건 추가

• 같은 물건이 꽂혀 있지 않고, 멀티탭 공간에 여유가 없는 경우

  • dictionary에서 해당 물건의 갯수(value) -1
  • 멀티탭에서 뽑을 대상을 탐색해서 해당 물건을 멀티탭 리스트에서 remove 시킨뒤, 새로운 물건을 append 시킨다.
  • 멀티탭에서 뽑은 횟수(result) + 1

멀티탭이 꽉 차 있는 경우, 꽂혀있는 물건을 뽑는 기준은 dictionary에서 가장 value가 작은 물건을 멀티탭 리스트에서 제거하는 방식으로 구현하였다. 아래 코드는 20%까지 진행후 WC를 받은 코드이다.

틀린 코드

import sys

N, K = map(int, sys.stdin.readline().split())

plugs = list(map(int, sys.stdin.readline().split()))

counts = dict()
# 물건 갯수 dictionary 초기화
for plug in plugs:
    if plug not in counts:
        counts.setdefault(plug, 1)
    else:
        counts[plug] += 1

multitap = []
result = 0

for plug in plugs:
    if len(multitap) != N:
        counts[plug] -= 1
        if plug in multitap:
            continue
        multitap.append(plug)
    else:
        small = sys.maxsize
        small_plug = 0
        for plug in multitap:
            if small > counts[plug]:
                small = counts[plug]
                small_plug = plug

        counts[plug] -= 1
        if plug in multitap:
            continue
        multitap.remove(small_plug)
        result += 1
        multitap.append(plug)

print(result)

예제 입력 케이스들과 몇몇 반례 케이스들을 통과하였으나 아래와 같은 경우 반례가 생기게 됨을 확인하였다.

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

일 경우 [3, 2]가 멀티탭에 들어가 있는 상태에서 1과 2를 번갈아가며 멀티탭에 꽂아야하기 때문에, 2를 뽑고 1을 다시 꽂는 과정을 반복하기보다는 가장 나중에 사용되는 3을 뽑고 1을 멀티탭에 꽂아 두는 편이, 반복되는 1 2 1 2 ... 에서 콘센트를 뽑는 횟수의 최솟값을 보장하기 쉬워진다.

내가 짠 오답 코드에서는 전체를 기준으로 단순하게, 멀티탭에 있는 물건의 잔여 횟수가 낮다면 뽑히는 대상이 되므로, 3이 뽑히는것이 아니라 2가 뽑히게 되어 1과 2가 뽑히는 과정이 반복되어 실제 답인 2가 아니라 7이 정답으로 출력되게 된다.

이를 개선하기 위해서는 다음과 같이 코드를 개선하여 AC를 받을 수 있었다.

정답 코드

import sys

N, K = map(int, sys.stdin.readline().split())
plugs = list(map(int, sys.stdin.readline().split()))

multitap = []
result = 0
for i in range(K):
    if plugs[i] in multitap:
        continue

    if len(multitap) != N:
        multitap.append(plugs[i])
        continue

	# 뽑을 물건의 번호
    pop_plug = 0
    # 멀티탭에 있는 물건 중 가장 나중에 사용될 예정인 물건
    late_use_index = 0

    for plug in multitap:
    	# 멀티탭에 있는 물건 중에 이후에 다시 등장하지 않는 물건이라면 바로 뽑는다
        if plug not in plugs[i:]:
            pop_plug = plug
            break
        # 멀티탭에 있는 물건이 모두 이후에 등장하는 물건들이라면
        elif plugs[i:].index(plug) > late_use_index:
        	# 그 중에서 가장 나중에 등장하는 물건을 찾아서
            late_use_index = plugs[i:].index(plug)
            # 뽑을 대상으로 지정한다.
            pop_plug = plug
    result += 1
    # 멀티탭에서 뽑을 대상의 인덱스를 찾고, 해당 자리를 새로운 물건으로 교체한다.
    multitap[multitap.index(pop_plug)] = plugs[i]

print(result)

전체적인 접근 방법은 유사하나, 멀티탭에서 뽑는 대상을 고르는 기준이 다르다. 기존에는 단순하게 멀티탭에 꽂힌 대상의 dictionary value(잔여 물건 갯수)가 작다면 멀티탭에서 제거했다면, 정답 코드에서는 멀티탭에 꽂혀있는 물건들로 현재 멀티탭에 꽂으려고 하는 물건부터 남은 물건들까지를 탐색하여, 멀티탭에 꽂힌 물건 중 가장 나중에 쓰일 물건을 멀티탭에서 뽑아낸다.

이렇게 가장 늦게 멀티탭에 꽂힐 물건을 먼저 뽑게 되면, 상대적으로 다른 물건들을 뽑을 때보다 멀티탭 리스트에 변화를 적게 하도록 보장할 수 있게 된다.