백준 1715번: 카드 정렬하기 파이썬 코드(우선순위 큐)

https://upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Python-logo-notext.svg/600px-Python-logo-notext.svg.png

#1715

import heapq
import sys

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

heap = []
carculate = []

for _ in range(n):
    card = int(sys.stdin.readline())
    heapq.heappush(heap, card)


while len(heap) > 1:
    temp1 = heapq.heappop(heap)
    temp2 = heapq.heappop(heap)
    carculate.append(temp1 + temp2)
    heapq.heappush(heap,temp1 + temp2)

print(sum(carculate))

설명

숫자끼리 더하면서 생기는 연산을 모았다가 더하면 되는 문제이다. 다만 적은 수끼리 더하는 것이 연산이 적기 때문에, 우선순위 큐를 사용해야한다. 더한 값은 다시 힙큐에 넣어줘야한다. while heap:을 사용하지 않은 이유는 pop이 두 번씩 되기 때문이다.

 

문제점

괜히 바보같이 주어진 수의 갯수가 짝수 개일때와 홀수 개일때 나눠서 연산해야하는 줄 알고 괜히 복잡하게 코드를 짰다가 다 지워서 다시 깔끔하게 작성하였다.