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

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

예제

조건

• 시간 제한: 2초
• 메모리 제한: 128MB

---

🔔 본 문제를 수월하게 풀기 위해서는, 우선순위 큐 & 힙 큐 에 대한 이해가 필요하다!

🔍우선 순위 큐?

• 큐 & 스택 과 비슷하지만, 원소들은 각각 우선순위를 가지고 있다.

• 힙(heap) 이라는 자료구조를 통해서 구현할 수 있다.

• 하나의 원소를 우선순위를 지정하여 추가하는 함수인 push , 가장 높은 우선순위의 원소를 큐에서 제거하고 반환해주는 함수인 pop 으로 해당 자료구조를 이용할 수 있다.

🧐 힙(heap)?

• 완전 이진트리(Complete Binary Tree)로, 부모 노드의 값이 자식 노드의 값보다 항상 큰 Max Heap과, 항상 작은 Min Heap으로 나뉜다.

Max Heap

Min Heap

---

💻 Python에서의 우선순위 큐

1. PriorityQueue

선언 및 초기화

from queue import PriorityQueue

q1 = PriorityQueue() 
q2 = PriorityQueue(maxsize=10) # maxsize로 크기 제한 가능

원소 추가

• .put(item)

q1.put(3)
q1.put(5)
q1.put(7)

q2.put((1, 'apple')) # (우선 순위, 값)의 형태로도 저장 가능

원소 삭제 & 반환

• .get()
• 기본적으로는 Min Heap으로 구성되기 때문에, 작은 수부터 반환된다.

q1.get() # 3 출력
q1.get() # 5 출력
q2.get()[1] # 우선순위 1의 값을 출력한다. apple 출력

2. heapq

• PriorityQueue 보다 속도가 빠르기 때문에, 일반적으로 더 많이 쓰인다.

• 기본적으로 Min Heap 으로 구성되기 때문에, 만약 Max Heap으로 만들고 싶다면 push 시에 - 를 붙여주어야 한다.

• 메소드를 사용시에는 항상 앞에 heapq.을 붙여서 사용한다.

• heappush()와 heappop() 모두 O(logN)의 시간복잡도를 갖는다.

선언 및 초기화

• 초기화된 list 를 만들거나, 기존의 list를 heapify를 사용해 heap으로 변환한다.

import heapq

hq = []

lst = [4, 3, 1, 2, 5, 6]
heapq.heapify(lst)
print(lst) # [1, 2, 4, 3, 5, 6] 출력

원소 추가

• heapq.heappush(heap, item)

heapq.heappush(hq, 4)
heapq.heappush(hq, 1)
heapq.heappush(hq, 3)

원소 삭제 & 반환

• heapq.heappop(heap)

• 가장 우선순위가 높은 원소를 반환한다.

• 만약 반환하고 싶지 않다면, heap[0] 으로 접근할 수 있다.

heapq.heappop(hq) # 1 반환
print(heap[0]) # 3 출력

---

코드

import heapq
import sys
input = sys.stdin.readline

N = int(input())
deck = []
for _ in range(N):
    deck.append(int(input()))
heapq.heapify(deck) # heap으로 변환

if len(deck) == 1:  # 덱이 1개인 경우
    print(0)
    exit(0)
    
count = 0  # 총 비교 횟수
while len(deck) > 1:
    d1 = heapq.heappop(deck) # 가장 작은 개수의 덱
    d2 = heapq.heappop(deck) # 그 다음으로 작은 개수의 덱
    compare = (d1 + d2)      # 두 덱 비교
    count += compare
    heapq.heappush(deck,compare) # 다시 heap에 넣어줌

print(count)

1. 카드 덱을 deck에 추가한 후, heapify를 사용해 heap으로 변환한다.

2. 만약 덱이 1개라면, 0을 출력하고 종료한다.

3. 가장 작은 개수의 덱끼리 차례대로 비교해나가는 것이 효율적이기 때문에, 최소 힙을 사용한다.

• 만약 덱이 [10, 20, 90, 100] 일 경우, 작은 수부터 비교해나간다면 (10+20) + (30+90) + (120+100) 으로 총 370번의 비교가 필요하다.

• 그러나 (10+90) + (20+100) + (100+120) 으로 순으로 비교한다면 총 440번의 비교가 필요하기에 상대적으로 비효율적이다.

4. heappop을 사용하여 현재 상태에서 가장 작은 개수의 덱 2개를 반환한다.

• 두 덱을 비교한 횟수인 compare을 count에 추가한다.

• 다시 비교를 해주기 위해 heappush를 사용하여 heap에 넣어준다.

5. 최종적으로 덱의 개수가 1개가 남게 되면, 모든 비교를 마친 것이기에 반복을 종료하고 count를 출력한다.

---

느낀 점 & 배운 점

1. 한 단계 더 어려운 문제로 나아가기 위한 개념인 우선순위 큐 & 힙 큐에 대해서 공부할 수 있어 유익했다!

2. 당분간은 heapq를 활용하는 문제를 풀면서 반복 숙달해야겠다.