[백준 1700번] 멀티탭 스케줄링 (Python3)

import sys
input = sys.stdin.readline

N,K = map(int,input().split())

seq = [*map(int,input().split())]

inuse = set()
cnt = 0
for i in range(K):
  if len(inuse) == N and seq[i] not in inuse:
    willuse = set()
    for j in range(i+1,K):
      if seq[j] in inuse:
        Pop = seq[j]
        willuse.add(seq[j])
        if len(willuse) == N:
          break
    if len(willuse) == N:
      inuse.remove(Pop)
    else:
      for Pop in inuse-willuse:
        inuse.remove(Pop)
        break
    cnt += 1
  inuse.add(seq[i])

print(cnt)

 

아이디어를 떠올리기는 쉬웠는데, 그게 맞는지를 판단하기가 어려운 문제였다.

 

내가 푼 알고리즘은 이러하다.

1. 사용할 물건을 inuse set에 넣는다.

2. 만약 set의 길이가 N보다 크고, 다음에 들어올 물건이 inuse 안에 없다면 3~6번

3. 앞으로 사용할 물건 중 inuse에 있는 물건을 willuse set에 N개까지 담는다. (inuse가 N개이므로)

4. 만약 willuse의 길이가 정확히 N이라면 가장 마지막에 담은 물건을 제거

5. 만약 willuse 길이가 N보다 작다면 willuse에 속해있지 않은 물건 중 아무거나 하나 제거

6. 제거할때마다 cnt +1

7. 결과 출력

 

 

여담) 몰랐는데 내 풀이가 파이썬 기준 성능 1위였다. 어쩐지 자꾸 풀이 읽었다고 알림이 뜨더라...