이것이 코딩 테스트다 PART3 with python : 정렬

이것이 코딩 테스트다 PART3 with python : 정렬

26. 카드 정렬하기 (난이도 2)

10,20,40장의 묶음이 있다면 10 + 20 = 30, 30 + 40 = 70
(10+20)+(30+40) = 100

import heapq

n = int(input())

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

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)

# 모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조
# 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2) 보다 작거나 같은 최소 힙의 형태로 정렬된다.   
# heapq.heappush(heap, item) : item을 heap에 추가
# heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
# heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )