[Python] boj no. 1700 : 멀티탭 스케줄링

Problem

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

Idea

플러그를 빼는 횟수를 최소로 하기 위해서는 다음 사용 순서가 가까운 전기용품을 최대한 빼지 않아야 한다. 이는 전기용품과 그 용품이 다음에 사용될 순서를 관리해야 함을 의미한다. 따라서, 현재 플러그에 꽃혀 있는 전기용품들의 집합인 plug를 (전기용품 번호, 다음에 사용될 순서)와 같은 형태로 관리했다.

plug에 삽입 및 삭제 연산을 다음과 같은 기준으로 구현했다.

1. 전기 용품을 플러그에 추가할 때마다 전기용품 순서 리스트를 탐색하여 다음 사용 순서와 함께 삽입한다. 사용 순서가 없을 경우 101로 설정한다(K <= 100).
2. plug의 길이가 N 미만이면, 즉 플러그에 남은 자리가 있으면 전기 용품을 추가한다.
3. plug의 길이가 N 이면, 즉 플러그가 꽉 찼으면
   • 플러그에 이미 있는 전기용품의 순서일 경우, 해당 전기 용품의 다음 사용 순서를 최신화한다.
   • 플러그에 없는 전기용품의 순서일 경우, 사용 순서가 가장 늦은 전기용품을 삭제하고 현재 순서를 삽입한다. 이후, 교체 횟수를 +1 한다.

Code

import sys

input = sys.stdin.readline

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

plug = {}   # 전기용품 : 해당 전기용품의 다음 사용 순서
sol = 0
for i in range(K):
    for j in range(i+1, K):
        if schedule[i] == schedule[j]:
            next = j
            break
    else:   # schedule 내에 해당 전기용품 사용이 없으면 마지막 사용순서 할당, K <= 100
        next = 101

    if schedule[i] in plug.keys() or len(plug) < N: # plug 내에 이미 전기용품이 꽂혀 있는 경우 or 플러그가 꽉차지 않은 경우
        pass    # 해당 전기용품 사용순서만 초기화(추가)
    else:
        change = max(plug, key=plug.get)    # 플러그 내에서 가장 나중에 사용되는 전기용품 선택.
        plug.pop(change)    # 플러그에서 뽑음.
        sol += 1

    plug[schedule[i]] = next

print(sol)        

Comment