[Python] 백준 / gold / 1715번 (카드 정렬하기)

문제 링크 : https://www.acmicpc.net/problem/1715

그리디 알고리즘 문제이다.
문제를 해석해보면, 카드 묶음 중에 가장 작은 카드 2세트를 계속 해서 섞는 행위를 반복하면 됨을 알 수 있다.
최솟값을 계속해서 pop해야 할 때 정말 적절한 자료구조가 있다 -> Heap
파이썬의 heapq 라이브러리를 이용해서 풀 수 있었다.

정답 코드

import sys
import heapq
N = int(input())
card = []

for _ in range(N):
    heapq.heappush(card, int(sys.stdin.readline()))

answer = 0

while len(card) > 1:
    first = heapq.heappop(card)
    second = heapq.heappop(card)

    answer += (first + second)
    heapq.heappush(card, (first + second))

print(answer)