[백준 20136] 멀티탭 스케줄링 2 (Python)

20136번: 멀티탭 스케줄링 2

지금 포스트를 작성하는 시점으로부터 약 1달 전에 멀티탭 스케줄링 1탄을 리뷰한 적이 있었습니다.

[백준 1700] 멀티탭 스케줄링

문제 내용은 같지만 멀티탭 스케줄링 2탄에서는 비현실적인 멀티탭을 다룹니다. 무려 멀티탭 구멍 갯수가 50만개나 됩니다!

1탄 복기하기

1탄에서는 어떻게 문제풀이를 했는 지 다시 기억을 되살려 봅시다.

1. 멀티탭에 꽃아야 할 물건이 들어온다.
2. 이미 꽃혀 있거나 멀티탭에 비어있는 구멍이 있다면, 바로 멀티탭에 물건을 꽂는다.
3. 하지만 해당 물건이 꽃혀 있지 않고 멀티탭이 비어있지 않다면 멀티탭에 꽃혀있는 물건들 중 가장 나중에 사용될 물건을 뽑고, 멀티탭에 꽃아야 할 새 물건을 멀티탭에 꽃는다. 이때 교환이 이루어지므로 카운터가 1 올라간다.
4. 이는 OPT 알고리즘과 일치하는 알고리즘이다.

1탄의 문제풀이의 핵심은 맨 나중에 교체되는 물건을 교환하는 것이었습니다. 맨 나중에 교체되는 물건을 찾으려면 각 꽃혀있는 물건들이 다음에 언제 다시 사용하는지 구해야 하고, 이를 구하려면 입력된 멀티탭 사용 리스트를 선형 순회해야 합니다. 선형 순회를 하는데 걸리는 최악의 시간  O(K), 꽃혀있는 물건들에게 이를 전부 적용해야 하므로 O(N), 마지막으로 멀티탭 리스트에 들어있는 모든 물건들에게 전부 적용해야 하므로 O(K)입니다. 이를 전부 합치면 시간 복잡도가.

가 됩니다. 1탄에서는 N, K가 100이하였기 때문에 최대가 100만번 반복이지만 2탄에서는 억단위가 넘어가기 때문에 시간초과가 발생합니다.

2탄 문제 풀기

2탄 문제의 핵심은 1탄 풀이에서 최적화를 진행해야 한다는 점 입니다. 즉, OPT 형태의 알고리즘을 유지하되, 여기서 최적화를 어떻게 해야 할 지 고민해야 합니다.

우선 멀티탭에 꽃힌 물건이 언제 다시 사용되는지에 대한 알고리즘을 최적화 할 수 있을 것 같습니다. 물건 번호의 범위는 1 이상 K 이하 이므로 길이가 K+1인 배열을 선언합니다. 배열의 요소는 해당 물건의 번호가 위치하는 인덱스를 넣는 리스트 입니다.

idxes = [list() for _ in range(k+1)]
a = list(map(int, input()[:-1].split())

for i in range(k):
	idxes[a[i]].append(i)

그리고 현재 멀티탭에 꽃혀있는 물건들이 언제 들어온 물건인지 idxes에 대한 인덱스로 표현하는 배열을 선언합니다.

next_k = [0] * (k+1)

for i in range(k):
	e = a[i]
    
    # ... 생략 ...
    
    # 새 물건 꽃기
    next_i = 0
    if next_k[e] == len(idxes[e]) - 1:
    	# 이번 물건이 e번 물건 중 맨 마지막으로 들어온 물건
        next_i = 1_000_000	# INF 설정
    else:
    	next_k[e] += 1
        next_i = idxes[e][next_k[e]]

이렇게 되면 다시 사용하게 되는 시점을 구하는 시간 복잡도는 next_k[e]의 카운터만 올려서 idxes[e][next_k[e]]값을 가져오면 되므로 O(K)에서 O(1)로 줄게 됩니다. 이로써 시간복잡도가 줄게 되었습니다.

N=50만, K=50만이면 여전히 억단위 입니다. 여전히 시간 초과가 발생하기 때문에 더 줄여야 합니다. 다음 사용되는 시점을 구하는 알고리즘은 최적화가 완료되었지만 가장 나중에 다시 사용되는 물건을 찾으려면 멀티탭에 꽃혀있는 물건들을 전부 순회해야 하므로 O(N)이라는 시간이 걸립니다. 이부분을 최적할 할 수 있을 것 같습니다.

방법은 쉽습니다. 우선순위 큐를 이용하면 되며 이때 큐에 들어가는 요소는 (다시 사용되는 시점, 물건 이름)이 되고 정렬 기준은 가장 나중에 사용되는 시점이 맨 앞으로 오게 됩니다. 즉, 일일히 멀티탭을 순회하는 대신 멀티탭에 꽃혀있는 물건들을 우선순위 큐에 집어넣어, 나중에 가장 나중에 사용하게 되는 요소만 한번에 뽑아 제거하면 됩니다. 이로써 시간 복잡도는

이 됩니다. (우선순위 큐에서 데이터를 뽑는 시간은 logN 입니다.) 이로써 N=50만, K=50만으로 집어넣어도 실행 횟수는 천만 단위로 줄게 됩니다.

솔루션 코드 (Python)

이번엔 오랜만에 파이썬으로 구현했습니다

코드 보기

import sys
import heapq

input = sys.stdin.readline

n, k = map(int, input()[:-1].split())
a = list(map(int, input()[:-1].split()))
idxes, q = [list() for _ in range(k+1)], []
current, next_k = [False] * (k+1), [0] * (k+1)
cnt, ans = 0, 0

for i in range(k):
    idxes[a[i]].append(i)

for i in range(k):
    e = a[i]

    if cnt == n and not current[e]:
        _, v = heapq.heappop(q)
        current[v] = False
        ans += 1
        cnt -= 1
    
    # 다음 위치하는 인덱스 찾고 저장
    next_i = 0
    if next_k[e] == len(idxes[e]) - 1:
        # 이미 끝에 다다른 경우
        next_i = 1_000_000 # 맨 마지막
    else:
        next_k[e] += 1
        next_i = idxes[e][next_k[e]]
    # 저장
    if not current[e]:
        cnt += 1
        current[e] = True
    heapq.heappush(q, (-next_i, e))

print(ans)