[Python/파이썬] 백준 1700번 멀티탭 스케줄링

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

코드

n, k = map(int, input().split())
orders = list(map(int, input().split()))

answer = 0
multitap = set()
for i in range(k):
    # 이미 꽂혀있는지 확인
    if orders[i] in multitap:
        continue
    # 빈 칸이 있는지 확인
    if len(multitap) < n:
        multitap.add(orders[i])
        continue
    # 교체
    change_plug = -1
    max_latest_use = -1
    for plug in multitap:
        if plug not in orders[i+1:]:
            change_plug = plug
            break
        latest_use = orders[i+1:].index(plug)
        if latest_use > max_latest_use:
            change_plug = plug
            max_latest_use = latest_use
    multitap.remove(change_plug)
    multitap.add(orders[i])
    answer += 1
print(answer)

 

멀티탭에 빈 칸이 있다면 거기에 꽂고, 아니라면 가장 나중에 다시 사용되는 플러그를 찾아서 뽑고 거기에 꽂으면 된다. 물론 이미 꽂혀있는 플러그라면 이 과정이 다 필요없다.

 

그래서 전기용품의 순서를 저장해둔 배열인 `orders`를 순회하며 다음 과정을 반복한다.

1. 이미 꽂혀있는지 확인. 이미 꽂혀있는 경우에는 아래 과정을 해볼 필요가 없으므로 먼저 확인해보는 것이 필요하다.

2. 빈 칸이 있는지 확인. 만약 multitap 배열의 크기가 n보다 작다면 멀티탭의 N개 구멍을 모두 사용하지 않고 있는 것이므로 빈 칸에 꽂아주면 된다.

3. 멀티탭에 이미 꽂혀있는 플러그 중 다시 사용 안되거나 가장 나중에 사용될 플러그를 찾아서 교체하기. 다시 사용되는 순서가 가장 나중인 플러그를 빼고 새로운 플러그를 꽂아야 최소한으로 플러그를 빼면서 작업을 모두 완료할 수 있다.