[힙] 백준 #1715 카드 정렬하기 - Python

🗂️ 문제

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

 

 

💡 접근법

10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

즉, 카드 묶음의 개수가 적은 것끼리 먼저 비교하는 방법이 가장 효율적이다.

 

이를 구현하기 위해 최소 힙을 사용한다. 만약 최소힙을 사용하지 않고 일반 정렬로 구현한다면, 매번 새로운 카드 묶음이 추가될 때매대 새로 정렬을 수행해야 한다.

하지만, python에서 sort()의 시간 복잡도는 O(nlogn)이므로 해당 방법으로 문제를 풀 경우 최악의 경우 O(n^2 logn)이라는 시간 복잡도를 가지게 되므로 시간 초과에 직면하게 된다.

 

여러 번의 정렬이 필요한 경우에는 시간 초과가 발생할 확률이 높기 때문에, 최소 힙을 통해 구현하는 방법을 떠올려 보자.

😎 내 코드

import sys
import heapq as hq

N = int(sys.stdin.readline())
card_list = []

for _ in range(N):
    card_list.append(int(sys.stdin.readline()))

hq.heapify(card_list)

cnt = 0
for _ in range(N-1):
    a = hq.heappop(card_list)
    b = hq.heappop(card_list)
    hq.heappush(card_list, a + b)
    cnt += a + b

print(cnt)

 

✅ 정답 확인