#290 백준 파이썬 [1715] 카드 정렬하기

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

 

SOLUTION

우선 순위 큐를 힙으로 구현하여 사용할 수 있다.

알고리즘은 다음과 같다.

 

0) 총 비교한 횟수(answer)를 0으로 둔다.

1) 현재의카드 묶음(card_deck) 중 가장 작은 2개의 카드 묶음을 꺼낸다.

2) 두 개를 더한 값 = 현재 단계에서 비교한 횟수

3) 두 개를 더한 값을 총 비교한 횟수에 더해준다.

4) 두 개를 더한 값을 다시 카드 더미 안에 넣는다.

5) 1 ~ 4 과정을 힙에 하나의 덱만 남을 때 까지 반복한다.

 

PYTHON CODE

import heapq
import sys

N = int(input())
card_deck = []
for _ in range(N):
    heapq.heappush(card_deck, int(sys.stdin.readline()))


if len(card_deck) == 1: #1개일 경우 비교하지 않아도 된다
    print(0)
else:
    answer = 0
    while len(card_deck) > 1: #1개일 경우 비교하지 않아도 된다
        temp_1 = heapq.heappop(card_deck) #제일 작은 덱
        temp_2 = heapq.heappop(card_deck) #두번째로 작은 덱
        answer += temp_1 + temp_2 #현재 비교 횟수를 더해줌
        heapq.heappush(card_deck, temp_1 + temp_2) #더한 덱을 다시 넣어줌
    
    print(answer)