[우선순위 큐, 힙] 백준 1715번 카드 정렬하기 with Python3

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

문제

 

내 풀이

import sys
import heapq

n = int(sys.stdin.readline())

heap = []

for i in range(n):
    heapq.heappush(heap, int(sys.stdin.readline()))


if len(heap) == 1:  # 1개일 경우 비교하지 않아도 됌
    print(0)
else:
    answer = 0
    while len(heap) > 1:  # 1개일 경우 비교하지 않아도 됌
        temp_1 = heapq.heappop(heap)  # 제일 작은덱
        temp_2 = heapq.heappop(heap)  # 두번 째로 작은덱
        answer += temp_1 + temp_2  # 두덱을 비교한 횟수를 answer에 넣어줌
        heapq.heappush(heap, temp_1 + temp_2)  # 더한 값을 다시 덱에 넣어줌
        # 이렇게 하면 계속해서 제일 작은 덱 두개를 합한 값을 비교횟수 answer 에 추가할수있다!

    print(answer)

출처:https://claude-u.tistory.com/341

해설

출처에 있는 풀이 과정을 참고해서 구현했다.

 

힙의 특성을 사용해 다시 비교값을 힙에 넣으면 알아서 제일 작은 덱을 뽑아 낼 수 있음을 처음엔 생각하지 못했다.