카드 정렬하기(BOJ 1715)

카드 정렬하기

heapq 모듈을 사용하여 쉽게 우선순위 큐를 구현 할 수 있다.

테스트 케이스

7
10
20
40
100
30
20
50

과정은 다음과 같다.

1. [10, 20, 20, 30, 40, 50, 100]
2. [20, 30, 30, 40, 50, 100]
3. [30, 40, 50, 50, 100]
4. [50, 50, 70, 100]
5. [70, 100, 100]
6. [100, 170]
7. [270]

heapq.heapush(리스트, 숫자) 이런식으로 집어 넣고 heapq.pop(리스트) 하면 가장 작은 숫자가 나온다

코드

import sys
import heapq
input = sys.stdin.readline

# heapq.heappop -> 작은거 순서대로 뽑아옴

card = []
total = 0
N = int(input())
for _ in range(N):
    heapq.heappush(card, int(input()))
    
if len(card) == 1:
    print(0)
else:
    while len(card) > 1:
        tmp = heapq.heappop(card) + heapq.heappop(card)
        total += tmp
        heapq.heappush(card, tmp)
    print(total)