[Python 3] BOJ - 1700 "멀티탭 스케줄링"

 # 문제 링크

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

1700번: 멀티탭 스케줄링

 

 # 풀이

 개인적으로 이 문제의 핵심은 그리디 알고리즘이라고 생각한다. 왜냐하면 현재 모든 구멍이 사용중이라면 어떤 하나를 뽑을 때 가장 나중에 사용할 전자기기를 뽑는 것이 최적이기 때문이다. 아주 간략한 증명은 다음과 같다. 현재 구멍이 모두 사용중이고 다음에 써야 할 전자기기를 A라고 하자. 만일 이 때 A가 구멍에 꽂혀있다면 A를 굳이 뽑아야 할 필요는 없다. 만약 A를 뽑는다면 명확히 손해이기 때문이다.

 따라서 현재 구멍이 가득차 있다면, 구멍을 사용하고 있는 전자기기들 중에서 다음에 사용할 시간이 가장 먼 전자기기를 뽑고 그 자리에 새로운 전자기기를 꼽으면 정답을 구할 수 있다

 

 # 코드

import sys, bisect, heapq

# 입력부
k, n = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

# powered : 현재 전자기기 i가 가장 마지막으로 꽃힌 시점을 저장하는 리스트
powered = [-1] * (max(arr) + 1)

# time : 각 전자기기를 key, 전자기기를 꽃아야 하는 시점의 리스트를 value로 갖는 dictionary
time = dict().fromkeys(set(arr))

# ans : 플러그를 뽑은 횟수
ans = 0

# 전자기기를 꼽는 시점을 time에 업데이트
for i in time:
    time[i] = []
for i in range(n):
    time[arr[i]].append(i)
    

for i in range(n):
    # total : 현재 꽂힌 전자기기의 갯수
    total = 0
    for j in powered:
        if j != -1:
            total += 1
    # 남는 구멍이 있다면 꼽음
    if total < k:
        powered[arr[i]] = max(powered[arr[i]], i)
    else:
        # 남는 구멍이 없지만 이미 사용중이라면 시점만 갱신
        if powered[arr[i]] != -1:
            powered[arr[i]] = max(powered[arr[i]], i)
            continue
        # 전체 구멍이 사용중이면서 이미 사용중인 전자기기가 아니니까 무조건 횟수 증가
        ans += 1
        q = []
        for j in range(len(powered)):
            # 이미 사용중인 전자기기를 찾음
            if powered[j] != -1:
                # idx : 전자기기가 마지막으로 꽂힌 시점으로부터 그 다음 사용할 시점의 인덱스
                idx = bisect.bisect_right(time[j], powered[j])
                # 만일 더 이상 사용할 일이 없다면 최소 힙에 음의 무한대값을 넣는다
                if idx == len(time[j]):
                    heapq.heappush(q, (-9876543210, j))
                # 사용할 일이 있다면 최소힙에 가장 가까운 미래에 사용할 시간을 넣는다
                else:
                    heapq.heappush(q, (-time[j][idx], j))
        # 가장 나중에 쓸 전자기기를 뽑고 콘센트를 갱신
        _, num = heapq.heappop(q)
        powered[num] = -1
        powered[arr[i]] = max(powered[arr[i]], i)
        
# 정답 출력
print(ans)