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

풀이

멀티탭이 꽉차 있으면 다음에 쓸 일이 없는 것 우선 빼고, 모든 기기가 전부 다음에 또 사용이 된다면 멀티탭에 끼워 놓은 것들 중 가장 나중에 사용되는 것을 우선적으로 뺀다.

도움이 된 반례

2 15
3 2 1 2 1 2 1 2 1 3 3 3 3 3 3
# answer 2
# output 3

3 14
1 4 3 2 5 4 3 2 5 3 4 2 3 4
# answer 4
# output 5

코드

import sys
from collections import Counter
input = sys.stdin.readline

n, k = map(int, input().split())
m = list(map(int, input().split()))
multitab = set()
counter = Counter(m)
answer = 0
for i, x in enumerate(m):
    counter[x] -= 1
    if x in multitab:
        continue
    if x not in multitab and len(multitab) >= n:  # 꽂혀있지 않은데 멀티탭이 꽉차있으면
        for a in multitab:  # 다음에 쓸일 없는것 우선으로 빼기
            if counter[a] == 0:
                multitab.remove(a)
                answer += 1
                break
        else:
            temp_set = set()
            for j in range(i, k):
                if m[j] in multitab:
                    temp_set.add(m[j])
                if len(temp_set) == n:
                    multitab.remove(m[j])
                    break
            answer += 1
    multitab.add(x)
print(answer)