[백준] 멀티탭 스케줄링

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

1700번: 멀티탭 스케줄링

 

플러그를 빼야 하는 상황이 생기면 꽂은 플러그 중 더 이상 사용하지 않거나 사용한다면, 가장 나중에 사용될 플러그를 뽑으면 된다.

 

N = 2, K = 7 이고, 

plug = [2, 3, 2, 3, 1, 2, 7] 를 예로 들면, usage = {2: deque([0, 2, 5]), 3: deque([1, 3]), 1: deque([4]), 7: deque([6])}) 를 만들어 해당 전기용품을 키로 값은 순서들을 담은 deque로 한다.

 

temp 는 멀티탭이라고 생각하면 된다.

temp 에 2와 3을 넣으면, queue 에는 [(-3, 3), (-2, 2)] 이다. 즉, (3+1)번째 순서에 3이 오고 (2+1)번째 순서에 2가 있다는 의미로 temp의 크기가 현재 N = 2 이기 때문에, 2, 3이 아닌 새로운 전기용품의 플러그를 꽂을 때 temp = {2, 3} 에서 순번이 높은 3의 플러그를 빼야 한다는 것을 알 수 있다. (popleft() 로 현재 순번을 보내고 다음 순번을 queue 에 담는다. 또한, 순번이 높은 것을 먼저 빼야 하기 때문에 순번에 -1을 곱한 값을 담는다.)

 

만약, 다음 순번이 없는 경우 더 이상 사용하지 않으므로 플러그를 뺄 때 1순위가 되어야 하므로 (-101, i) 를 queue 에 담는다. (K <= 100)

 

queue 에는 temp 에 담길 때, 해당 전기용품의 다음 순번 또는 사용하지 않으면 101의 값을 queue에 담으므로 queue 에 값이 없거나, 중복된 i 값이 영향을 주거나 하는 일은 없다.

 

import sys, heapq
from collections import defaultdict, deque

N, K = map(int, sys.stdin.readline().split())
plug = list(map(int, sys.stdin.readline().split()))
usage = defaultdict(deque)
temp = set()
queue = []
answer = 0

for i in range(len(plug)):
    usage[plug[i]].append(i)
    
for i in plug:
    print(queue, temp)
    
    temp.add(i)
    usage[i].popleft()
    
    if len(temp) > N:
        answer += 1
        index, p = heapq.heappop(queue)
        temp.remove(p)
        
    heapq.heappush(queue, (-usage[i][0] if usage[i] else -101, i))
                
print(answer)