1715: 카드 정렬하기

풀이 시간

• 22m

구현 방식

• 카드 묶음의 크기가 작은 묶음들끼리 먼저 비교를 해주어야 총 비교 횟수가 최소가 된다
  -> 우선순위 큐를 이용

• heap에서 카드 묶음의 크기가 작은 묶음 두 개를 꺼내서 둘을 더한 값을 다시 heap에 넣는 과정을 len(heap)이 2이상일때까지 반복하면서 result를 갱신해주면 된다

코드

import sys
import heapq


N = int(sys.stdin.readline()[:-1])
bundle = []
for n in range(N):
    bundle.append(int(sys.stdin.readline()[:-1]))

heap = []
for n in range(N):
    heapq.heappush(heap, bundle[n])

result = 0
while len(heap) >= 2:
    tmp1 = heapq.heappop(heap); tmp2 = heapq.heappop(heap); tmp3 = tmp1 + tmp2
    result += tmp3
    heapq.heappush(heap, tmp3)

print(result)

결과