[python] 백준 1700 멀티탭 스케줄링

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

1700번: 멀티탭 스케줄링

문제 해결

• 순서대로 멀티탭을 꽂고 빼고 해야한다.
• 뒤에 같은 종류가 있으면 안빼고 바로 연결하면 된다.
• 혹은 멀티탭에 비어있는 것이 있으면 꽂으면 된다.
• 만약 현재 연결해야 하는 것이 있고 멀티탭에 연결되어 있는 물건 중 같은 종류가 없으면 한 종류의 물건을 빼야한다.
• 빼야 하는 것은 뒤에 물건들을 보고 연결할 필요가 없거나 가장 늦게 연결할 필요가 있는 것을 제거하는 것이 낫다.

CODE

from collections import Counter
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
M = list(map(int, input().split()))
V = set() # 멀티탭에 있는 것들 모음
memo = Counter(M) # 각 종류마다 몇 개가 있는지
ans =0

for i, x in enumerate(M):
    memo[x] -= 1
    if x in V: continue # 바로 연결하면 되서 뺄 필요x
    if x not in V and len(V) >=n: #멀티탭에서 한 개를 빼야할 때
        for a in V: # 멀티탭에 꽂혀 있는 것 하나씩 분석
            if memo[a] ==0: # 더이상 쓸 일이 없으면 뽑자
                V.remove(a)
                ans += 1
                break
        else: # 다 써야한다면 가장 늦게 필요한 것을 뽑는 것이 낫다.
            temp_set = set()
            for j in range(i,k):
                if M[j] in V:
                    temp_set.add(M[j])
                if len(temp_set) ==n:
                    V.remove(M[j])
                    break
            ans += 1
    V.add(x)
print(ans)