백준 1715: 카드 정렬하기(골드 IV) - Priority Queue

1715번: 카드 정렬하기

우선순위 큐를 사용하는 대표적인 문제인 것 같다.

문제 요약:

여러 장으로 구성된 덱들을 하나로 합칠 때, 최소 비교 횟수로 합칠 수 있는 방법

ex) 10장, 20장, 40장으로 구성된 덱에서 10장짜리와 20장짜리를 합치는데 30번의 비교가 들고 합쳐진 30장과 40장을 합칠때는 70번의 비교가 소요되어 총 100번의 비교가 수행. 만약 10장과 40장을 먼저 합치고 20장과 합친다면 (10+40) + (50 + 20) == 120이 되어 최소 비교횟수가 아님.

 

솔루션 (오답):

단순히 덱의 크기순으로 오름차순 정렬 하여 popleft()를 두 번 하여 합친 후 다시 appendleft() 를 하는 방식으로 구해볼 수 있을 것 같다.

위 경우의 반례:

입력:

4

1

1

1

1

위의 방법대로라면 (1+1) + (2 + 1) + (3 + 1) == 2 + 3 + 4 == 9

하지만 1,2번 덱과 3, 4번 덱을 합친 후 이 둘을 합치면 (1 + 1 ) + (1 + 1) + (2 + 2) == 8이 되버린다.

 

솔루션 (정답):

가장 작은 두개의 덱을 합쳤을 때, 이보다 작은 덱이 있을 경우 작은 덱들끼리 합치는 것이 더욱 비교횟수를 줄일 수 있다.

즉, 합치기 전이나 합치기 후나 가장 작은 2개를 뽑아야한다.

 

덱의 개수가 총 10만개로 주어졌다. 이때 가장 작은 두 가지 덱을 추출하려면 직관적으로 값을 삽입할때마다 정렬을 수행해 앞 두 개를 가져오면 된다. 하지만 이는 정렬 복잡도 (nlogN)과 n번 정렬하므로 (n^2logN)이 되는데, 덱의 최대 개수가 10만개이므로 시간 내에 수행할 수 없게된다.

효율적으로 최소 혹은 최대의 값을 매번 뽑아내는 문제에서는 우선순위 큐를 생각해내야한다. heap 자료구조를 사용해 삽입과 추출 모두 O(logN)으로 마무리 할 수 있다.

 

1. 만약 N이 1이면 비교할 것이 없으므로 답은 0

2. 우선순위큐(pq) 의 길이가 2가 되었을 경우, 마지막 비교이므로 이 둘을 더한 후 break

3. 그 외에 경우에서는 heappop으로 두 개의 가장 작은 덱을 빼내어 합하고, 합한 값을 다시 heappush 수행. 이때 result값에 앞서 빼낸 두 가지 값을 더해야 함. 

 

소스코드

import sys
import heapq
input = sys.stdin.readline

N = int(input())

pq = []
for _ in range(N):
    heapq.heappush(pq, int(input()))

pq.sort()

result = 0
while pq:
    if len(pq) == 2:
        result += sum(pq)
        break
    
    elif len(pq) == 1:
        result = 0
        break
        
    else:
        n1 = heapq.heappop(pq)
        n2 = heapq.heappop(pq)
        
        new_n = heapq.heappush(pq, n1+n2)
        
        result += n1+n2
        if len(pq) == 1:
            break
        
print(result)