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

- 문제

 

- 제출

최소한의 비교를 하려면 작은 묶음부터 나열한 후, 가장 작은 페어의 수를 더하고 더한 수를 나열된 리스트에 추가하고 또 나열하는 과정을 리스트에 숫자가 하나가 될 때까지 반복하면 된다. 

하지만 이 문제의 포인트는 바로 시간 초과 ㅠㅠ 그래서 구글링을 했더니 우선순위 큐를 사용해야 한다고 했다.

while문 안에서 계속 리스트에서 값을 꺼내고 넣고 정렬하는 과정을 반복하는 것이 시간이 너무 많이 걸려서 인 듯했다.. 그래서 값을 넣으면 가장 작은 값부터 자동으로 정렬되는 우선순위 큐를 사용해야 했다. ㅎㅎ 자료 구조 형태를 바꾸니 바로 해결!

 

import heapq

N = int(input())
cards =[] 
for _ in range(N):
    heapq.heappush(cards,int(input()) )

result = 0

while len(cards) > 1:
    a = heapq.heappop(cards)
    b = heapq.heappop(cards)
    result += (a+b)
    heapq.heappush(cards,a+b)
    
print(result)