카드 정렬하기

p.363

 

import sys
import heapq
input=sys.stdin.readline

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

result = 0

# 힙에 원소가 1개 남을 때까지
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)

 

* heapq는 넣기만 해도 정렬된다는 것을 이용

* deque나 stack으로 한 후 sort하는 것은 시간 초과가 남