백준|1715번|카드 정렬하기

문제설명
각각 카드의 수가 A, B인 두 묶음의 카드를 합쳐서 하나로 만드는데 필요한 비교의 횟수를 A+B라고 할 때, 많은 숫자 카드 묶음을 입력받고 이들을 두 묶음씩 합쳐나갈때 최소 몇번의 비교를 해야하는지 출력하는 프로그램입니다.

작동 순서
1. 입력받을 카드 뭉치의 숫자를 입력받습니다.
2. 각 카드 뭉치의 숫자를 입력받고 힙 형식으로 만들어줍니다.
3. 비교 숫자가 최소가 되기위해서는 최대한 작은 숫자의 카드뭉치들끼리 합쳐져야하므로 카드뭉치들중 카드 수가 가장 적은 2개의 뭉치를 가져옵니다.
4. 2개의 뭉치를 합치고 비교횟수를 count에 더해줍니다.
5. 카드뭉치가 하나가 되면 반복문을 중지합니다.
6. 카드뭉치를 모두 뭉치는데 필요한 최소의 비교횟수를 출력합니다.

소스코드

import heapq
import sys
card = []
count = 0
for i in range(int(sys.stdin.readline())):
    heapq.heappush(card, int(sys.stdin.readline()))
while len(card) > 1:
    s1 = heapq.heappop(card)
    s2 = heapq.heappop(card)
    heapq.heappush(card, s1+s2)
    count += s1+s2
print(count)

후기
자료구조의 중요성을 알게 되는 문제인것 같습니다. 처음에 작은 숫자들끼리 합해야 한다는 것은 알았지만 이를 배열로 구현하려고 해서 어려움을 겪었었는데 힙을 활용하여 쉽게 풀 수 있었습니다.