Coding Test

[백준] 카드 정렬하기

상상쓰 2021. 6. 9. 00:29

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

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

 

우선순위 큐(heapq) 를 이용해서 가장 작은 2개의 숫자의 합을 계산해주고 그 값을 또 queue 에 넣어준다. 이러한 과정을 반복하여 queue 에는 하나의 값만 남을 때까지 계속한다. 마지막으로 숫자의 합을 계속 더해준 answer 를 return 한다. 

 

import sys
import heapq

answer = 0
N = int(sys.stdin.readline())
queue = []
for i in range(N):
    heapq.heappush(queue, int(sys.stdin.readline()))

while len(queue) > 1:
    AB = 0

    for i in range(2):
        AB += heapq.heappop(queue)

    answer += AB
    heapq.heappush(queue, AB)

print(answer)