책너두 - 알고리즘 챌린지[17/20]

오늘의 문제 : 파일 합치기 3

문제가 쉽다고 생각했는데, 한 가지 실수를 했다.

처음에 풀 때, 값을 정렬하고 다시 리스트에 넣어주면 되겠다 생각했지만 우선순위 큐를 생각하지 못 했다(...) 당연히 시간초과.

우선순위 큐를 써야한다는 걸 힌트를 얻어 풀 수 있었다.

자료구조에 예민하다 생각했는데 쉬운 걸 놓칠 때 아쉽다 ㅠㅠ

import sys
from heapq import *

t = int(sys.stdin.readline())

for _ in range(t) :
    k = int(sys.stdin.readline())
    novels = list(map(int, sys.stdin.readline().split()))
    heapify(novels)
    ans = 0

    while len(novels) > 1 :
        foo, bar = heappop(novels), heappop(novels)
        ans += foo + bar
        heappush(novels, foo+bar)

    print(ans)