1715 카드정렬하기(heap 활용)

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

1715번: 카드 정렬하기

내가 푼 풀이(맞음)

import heapq

n = int(input())
heap = []
for i in range(n):
    x = int(input())
    heapq.heappush(heap, x)
result = 0
while(len(heap) != 1):
    sum = 0
    a = heap[0]
    heapq.heappop(heap)
    a += heap[0]
    heapq.heappop(heap)
    sum += a
    result += sum
    heapq.heappush(heap, sum)
    
print(result)

처음에 heap 안쓰고 list로 푸니까 시간 초과 떴었음, 그래서 heap으로 풀라는 힌트 살짝 보고 풀음

heap 쓸려면 import heapq 써야된다. 그리고 힙에 추가하려면 heapq.heappush(리스트 이름, 값)으로 한다.

그리고 힙의 0번째를 호출하면 무조건 최소값이 나온다. 하지만 1번째 자리가 그 다음으로 작은 값은 아니다. 그래서 heapq.heappop(리스트 이름)을 하면 가장 최소값이 삭제된다. 가장 최소값을 삭제하고 그 다음 최소값을 찾는다.