1715번 - 카드 정렬하기

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

1715번: 카드 정렬하기

이 문제를 풀 때 가장 중요한 점은 '우선순위 큐'를 사용한다는 것이다. 그리고 파이썬에는 heapq 모듈에 구현되어 있다. 

우선 카드의 수를 입력받은 리스트 A를 힙으로 바꾼다. 그리고 우선순위 큐는 우선순위가 낮은 값부터 pop하기 때문에 최솟값을 쉽게 구할 수 있다. 따라서 두 번의 pop을 통해 최솟값을 꺼내고 그 둘을 더한 뒤 다시 우선순위 큐에 넣는다.

이 과정을 진행하면 최솟값끼리의 합이 계속 진행되기 때문에 최소한의 비교로 카드를 정렬할 수 있다. 

만약 우선순위 큐에 1개의 값만 남아있다면 두 개의 원소를 뺄 수 없고 비교가 종료되었다는 뜻이니 그때 whlie 문을 종료하고 값을 출력한다.

# 카드 정렬하기
import sys
from heapq import *
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]
heapify(A)
answer = 0

while True:
    if len(A) == 1:
        print(answer)
        break
    a = heappop(A)
    b = heappop(A)
    value = a+b
    heappush(A, value)
    answer += value