[백준/python/1715]카드 정렬하기

문제링크 : 카드 정렬하기

문제

이번 문제는 보자마자 작은 수부터 차례대로 합해야 한다는 아이디어가 생각났다. 그런데 단순구현으로 정렬을 사용해서 푸니까 시간초과라는 문제가 생겼다. 고민 끝에 자동으로 우선순위 큐가 완성되는 힙을 사용했다.

코딩테스트 문제를 풀 때도 시간초과가 날까봐 걱정되는 문제들이 있는데 heapq를 꼭 기억해야겠다.

import heapq

n=int(input())
card=[]
for i in range(n):
    heapq.heappush(card, int(input()))
sum=0
if len(card)==1:
    print(0)
else:
    while len(card)>1:
        result=heapq.heappop(card)+heapq.heappop(card)
        sum+=result
        heapq.heappush(card,result)
    print(sum)