백준 13975 파이썬 python : 파일 합치기 3 @@황소처럼 우직하게@@ 문제의 본질

푸는 방법은 다음과 같다

1. 파일들 중에서 제일 작은 두개를 뽑는다. 

2. 합친다

3. 합친걸 다시 파일들에 둔다.

반복한다

이 때 구현은 minq 를 사용하는 것이 효율적이다.

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)