[알고리즘] 카드 정렬하기

[문제] 카드 정렬하기
https://www.acmicpc.net/problem/1715

heapq 자료구조

우선순위 큐는 이진트리로 만들어진 자료구조이다.
우선순위 큐를 구현할 때는 내부적으로 최소 힙 혹은 최대 힙을 이용한다.
최소 힙을 이용하는 경우 값이 가장 낮은 데이터가 먼저 삭제되고,
최대 힙을 이용하는 경우 값이 큰 데이터가 먼저 삭제된다.
파이썬 라이브러리는 기본적으로 최소 힙 구조를 이용한다.

시간 복잡도

1. 리스트: 삽입 시간(O(1)) / 삭제 시간(O(N))
2. 힙: 삽입 시간(O(logN)) / 삭제 시간(O(logN))

문제 해결 hint

1. 항상 가장 작은 크기의 두 카드 묶음을 합쳤을 때가 최적의 해이다.
2. 하나의 카드 묶음이 남을 때까지 가장 작은 두개의 카드 묶음을 계속해서 합쳐 나간다.
3. 합쳐진 두개의 카드 묶음은 다시 삽입한다

import heapq

n = int(input())

heap = []
for i in range(n):
    data = int(input())
    heapq.heappush(heap, data)

result = 0

while len(heap) != 1:
    one = heapq.heappop(heap)
    two = heapq.heappop(heap)

    sum_value = one + two
    result += sum_value
    heapq.heappush(heap, sum_value)

print(result)