[백준 13975 골4] 파일 합치기 3 (heapq/greedy/python) -/3

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

이 외에도 복습이 필요한 링크: https://www.acmicpc.net/problem/21758
https://sodehdt-ldkt.tistory.com/m/53

내용은 그렇게 어렵지 않다.

import sys
input = sys.stdin.readline
import heapq

t = int(input())

for _ in range(t):
    n = int(input())
    lst = list(map(int, input().split()))
    ans = 0
    q = []
    for i in lst:
        heapq.heappush(q, i)
    while len(q) > 1:
        a = heapq.heappop(q)
        b = heapq.heappop(q)
        ans += a + b
        heapq.heappush(q, a + b)
    print(ans)

힙큐는 빈 리스트를 항상 넘겨줘야 한다는 점에 주의하자.
우선순위 큐와 같지만 우선순위 큐보다 좀 더 빠르다는 장점이 있다.

파이썬 라이브러리를 뜯어보면 우선순위 큐 자체가 애시당초 힙큐로 구현되어 있다.