문제 분석

멀티탭에 코드를 꽂는 순서를 스케줄링하는 문제로, 멀티탭의 수와 전자기기의 사용순서가 주어지면 코드를 뽑아야하는 최소 횟수를 구하는 문제이다.

보자마자 LRU, MRU같은 버퍼 스케줄링이 생각나서 어떻게 풀어야 할 지는 금방 떠올렸는데 교체할 전자기기를 선택하는 조건을 잘못 생각해서 시간을 많이 잡아먹었다.

Key idea

처음 접근은 멀티탭에 꽂혀있는 전자기기 중 현 시점 이후 가장 적게 사용되는 코드를 뽑으면 될 것이라고 생각하고 문제를 풀었다. 그런데 코드를 제출하고 첫 테스트케이스부터 오답이 나와 반례를 찾다가 풀이를 찾아봤는데, 가장 적게 사용되는 코드가 아니라 현 시점 이후 가장 나중에 사용되는 코드를 뽑아야 최적해를 구할 수 있었다.

잘 생각해보면 당연한게, LRU나 MRU등의 버퍼관리 정책에서도 가장 가까운 시점에 사용될 것으로 예상되는 버퍼는 남기고, 가까운 미래에 사용되지 않을 것 같은 페이지를 교체한다. 같은 논리로 이 문제에서도 가까운 미래에 사용되지 않는 전자기기를 선택해야 최소 교체 횟수를 구할 수 있다.

Solution

먼저 전자기기가 사용되는 시점을 각 기기의 이름을 key로 하여 position에 담고, 현재 멀티탭에 해당 전자기기가 꽂혀있는지를 나타내는 plug와 사용중인 전자기기의 수인 plugged를 초기화한다. 이후 순서대로 코드를 멀티탭에 꽂거나 멀티탭이 가득 찬 경우 코드를 교체한다. 이때 현 시점 이후 가장 나중에 사용되는 전자기기를 찾기 위해 코드를 꽂을 때마다 최대힙에 (사용시점, 전자기기 번호)를 push한다.

import sys
import heapq

n, k = map(int, sys.stdin.readline().strip().split(" "))
schedule = list(map(int, sys.stdin.readline().strip().split(" ")))

position = dict([])
plug = [False for _ in range(101)]
plugged = 0

for i, s in enumerate(schedule):
    if str(s) not in position.keys():
        position[str(s)] = []
    position[str(s)].append(i)

for k in position.keys():
    position[k].append(101)

hq = []

cnt = 0
for s in schedule:
    if not plug[s]:
        if plugged < n:
            plug[s] = True
            plugged += 1
        else:
            cnt += 1
            r, i = heapq.heappop(hq)
            plug[i] = False
            plug[s] = True
    else:
        hq.remove((-position[str(s)][0], s))

    position[str(s)].pop(0)
    heapq.heappush(hq, (-position[str(s)][0], s))

print(cnt)

• BOJ 1700 멀티탭 스케줄링