1715 - 카드 정렬하기

https://www.acmicpc.net/problem/1715

 

정답코드!

import sys
import heapq
input = sys.stdin.readline

n = int(input())

queue = []
for i in range(n):
    heapq.heappush(queue, int(input()))

res = []
while len(queue) >= 2:
    tmp1 = heapq.heappop(queue)
    tmp2 = heapq.heappop(queue)
    res.append(tmp1+tmp2)
    heapq.heappush(queue, tmp1+tmp2)

print(sum(res))

 

처음 문제에 접근한 방법은 정렬된 단순 queue를 사용해서 문제에 접근했다.

하지만 queue로 문제에 접근하면 한번 연산을 시행해줄때마다 계속해서 sort를 해줘야 했고 이 방법은 너무 비효율적이라 판단되어 폐기.

 

최종적으로 삽입과 삭제가 일어날때마다 최소값이 갱신되는 최소힙으로 문제에 접근했다.