[BOJ 1715번] : 카드 정렬하기

문제 링크 : https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

함께 올려주신 파일 합치기 문제와 유사해 금방 해결할 수 있었습니다!
양옆의 두 원소를 합치기 때문에 N - 1번의 연산을 수행해야 하는데요, 따라서 마지막 끝의 두 원소를 합치는 경우가 아닌 이상 더했던 요소를 언젠간 추가로 더하게 되므로 제일 작은 값 둘을 합치는 연산을 반복해야 합니다.

이를 구현하는 데에 수만 개의 원소가 존재해도 원소를 추가하고 빼는 동작이 O(logN)인 힙을 사용하면, 문제를 쉽게 해결할 수 있습니다!

import sys
import heapq

N = int(input())
heap = []
count = 0
tempCount = 0

for _ in range(N):
    temp = int(input())
    heapq.heappush(heap, temp)

for _ in range(N - 1):
    one = heapq.heappop(heap)
    two = heapq.heappop(heap)
    tempCount = one + two
    heapq.heappush(heap, tempCount)
    count += tempCount


print(count)

또 지금까지는 파이썬의 우선순위 큐를 PriorityQueue 라는 클래스를 불러와 구현했었는데, PriorityQueue를 사용하면 시간 초과가 나는 경우가 종종 있어 대신 heapq 모듈을 불러와 사용하는 것이 좋다고 하네요!

What's the difference between heapq and PriorityQueue in python?