[BOJ 1700] 멀티탭 스케줄링

1. 멀티탭에 빈 구멍이 있다면, 해당 구멍에 전기용품을 꽂는다
2. 이미 사용중인 전기용품이 있다면 다음 전기용품으로 넘어간다
3. 꽂을 구멍이 없다면, 꽂혀있는 전기용품 중에서 가장 나중에 사용되는 전기용품을 뽑고 그 구멍에 새로운 전기용품을 꽂는다

처음 배열을 순회하면서 각 전기용품마다 사용되는 인덱스를 덱으로 저장한다(맨 마지막은 INF)

from collections import deque

def print_dq(next_idx, K):
    for i in range(1, K + 1):
        print(i, next_idx[i])

N, K = map(int, input().split())
plugs = [0] * N
next_idx = [deque() for _ in range(K + 1)]

items = list(map(int, input().split()))
for i, item in enumerate(items):
    #print(i, item)
    next_idx[item].append(i)
for i in range(K + 1):
    next_idx[i].append(float('inf'))

answer = 0
for item in items:
    # if item is already on the plug -> O(n)
    if item in plugs:
        #print(item, 'is already exist')
        _ = next_idx[item].popleft()
        continue

    # if there is an empty space
    reset = False
    for i in range(N):
        if plugs[i] == 0:
            plugs[i] = item
            _ = next_idx[item].popleft()
            reset = True
            break
    if reset:
        #print(plugs)
        continue

    # get latest idx
    max_idx = -1
    reset_idx = -1
    for i, plug_item in enumerate(plugs):
        if next_idx[plug_item][0] > max_idx:
            reset_idx = i
            max_idx = next_idx[plug_item][0]
    
    _ = next_idx[item].popleft()
    plugs[reset_idx] = item
    answer += 1
    #print_dq(next_idx, K)
    #print(plugs, answer)

print(answer)