1700. 멀티탭 스케줄링

문제

백준 1700번 멀티탭 스케줄링

---

풀이

문제를 보자마자 페이징 기법이 생각났다.
처음에는 가장 많은 남은 순서로만 정렬해서 틀렸는데, 여러 케이스를 테스트해보고 앞으로 나올 순서를 먼저 고려하는 알고리즘으로 변경했더니 통과했다.

앞으로 꽂을 플러그를 미리 알 수 있기 때문에 뽑아야할 콘센트의 결정이 쉬워진다.

1. 꽂혀있음
2. 꽂혀있지 않음
   2-1. 멀티탭에 빈 공간 있음
   2-2. 멀티탭이 꽉 참 -> 정렬에 의해 마지막 원소 변경, 뽑은 횟수 증가

한 플러그에 대해 처리가 끝나면 멀티탭의 정렬이 필요한데,

1. 현재 플러그가 seq에 남은 경우
   -> 가장 먼저 등장하는 순서로 멀티탭 정렬
2. 남아있지 않은 경우
   -> 가장 많이 남아있는 순서로 멀티탭 정렬

n, k = map(int, input().split())
seq = list(map(int, input().split()))
plug = []
rem = [0] * (k+1)
cnt = 0
for s in seq: rem[s] += 1
while seq:
    s = seq.pop(0)
    if s not in plug:
        if len(plug) < n:
            plug.append(s)
        else:
            plug[-1] = s
            cnt += 1
    rem[s] -= 1
    if s in seq:
        plug.sort(key=lambda s:seq.index(s) if s in seq else 1000)
    else:
        plug.sort(key=lambda s:rem[s], reverse=True)
print(cnt)

---

부족한 점

직접 테스트케이스를 생각해내는 것이 쉽지 않다.
테스트케이스가 주어지지 않는 코테도 있기 때문에 연습이 필요하다.