📌 문제 요약

• 문제 이름: 1715번: 카드 정렬하기
• 알고리즘 분류: 자료 구조, 그리디 알고리즘, 우선순위 큐
• 사용 언어: Python 3

정렬된 두 묶음의 숫자 카드가 있을 때, 각 묶음의 카드의 수를 $A$, $B$라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 $A+B$ 번의 비교를 해야 합니다.
$N$개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 문제입니다.

---

💡 문제 접근 방법 (핵심 로직)

이 문제는 전형적인 그리디(Greedy) 알고리즘입니다. 총 비교 횟수를 최소화하려면 매 순간 "가장 크기가 작은 두 묶음을 골라서 합쳐야" 합니다. 일찍 합쳐진 묶음은 이후에 다른 묶음과 합쳐질 때마다 그 크기가 계속 누적되어 더해지기 때문입니다.

1. 매번 최솟값 2개 찾기: 가장 작은 두 묶음을 찾아 합치고, 그 새로운 묶음을 다시 기존 묶음들 사이에 넣고, 또다시 가장 작은 두 묶음을 찾아야 합니다.
2. sort()의 함정: 합칠 때마다 리스트에 append를 하고 sort()로 정렬을 다시 한다면, 시간 복잡도가 $O(N^2 \log N)$이 되어 최악의 경우($N=100,000$) 무조건 시간 초과가 발생합니다.
3. 해결책 - 우선순위 큐(heapq):
   데이터를 넣고 뺄 때마다 자동으로 정렬 상태(정확히는 최소 힙 구조)를 유지해 주는 파이썬의 heapq 모듈을 사용합니다. heapq.heappop()을 두 번 호출하면 가장 작은 두 수를 $O(\log N)$만에 뽑아낼 수 있습니다.

---

💻 코드 구현

import sys
import heapq

input = sys.stdin.readline

N = int(input())
C = [int(input()) for _ in range(N)]

hq = []
num = 0

# 입력값을 모두 최소 힙에 푸시
for c in C:
    heapq.heappush(hq, c)

# 힙에 원소가 1개 남을 때까지 반복
while len(hq) > 1:
    # 가장 작은 두 카드 묶음 빼기
    a = heapq.heappop(hq)
    b = heapq.heappop(hq)
    
    # 비교 횟수 누적
    num += a + b
    
    # 합친 카드 묶음을 다시 힙에 넣기
    heapq.heappush(hq, a + b)

print(num)

---

🚀 코드 최적화: heapify 활용하기

앞선 코드에서는 빈 리스트를 만들고 for문을 돌며 heapq.heappush()를 $N$번 반복하여 힙을 구성했습니다. 이 경우 데이터를 하나씩 삽입할 때마다 힙 구조를 재정렬하므로 시간 복잡도는 $O(N \log N)$이 됩니다.

하지만 파이썬의 heapq 모듈에는 이미 완성된 리스트를 한 번에 힙 자료구조로 변환해 주는 아주 강력한 함수인 heapq.heapify()가 있습니다. 이 함수는 상향식(Bottom-up)으로 힙을 구성하기 때문에 단 $O(N)$의 시간 복잡도만으로 리스트를 힙으로 만들어 줍니다.

이를 적용하여 코드를 훨씬 파이썬스럽게(Pythonic) 개선해 보았습니다.

import sys
import heapq

input = sys.stdin.readline

N = int(input())
# 리스트 컴프리헨션을 이용해 입력값을 바로 하나의 리스트로 만듦
hq = [int(input()) for _ in range(N)]

# O(N)의 시간 복잡도로 리스트를 즉시 최소 힙 구조로 변환
heapq.heapify(hq)

num = 0

while len(hq) > 1:
    a = heapq.heappop(hq)
    b = heapq.heappop(hq)
    
    num += a + b
    heapq.heappush(hq, a + b)

print(num)

for문과 heappush를 사용하던 초기화 과정이 heapify(hq) 단 한 줄로 깔끔하게 정리되었을 뿐만 아니라, 내부적인 실행 속도(상수 시간)와 메모리 효율성도 한층 더 끌어올릴 수 있었습니다. 앞으로 리스트 전체를 힙으로 바꿔야 할 때는 무조건 heapify를 적극 활용해야겠습니다!

🚨 트러블 슈팅 및 회고

• 엣지 케이스($N=1$)의 중요성: 카드가 처음부터 1묶음만 주어졌을 경우($N=1$), 다른 묶음과 비교할 필요 자체가 없으므로 정답은 0이 되어야 합니다. 코드를 짤 때 while len(hq) > 1: 이라는 조건을 걸어두었기 때문에, $N=1$일 때는 while문을 아예 타지 않고 초기값인 num = 0이 그대로 출력되어 예외 처리가 아주 매끄럽게 이루어졌음을 확인했습니다.
• 파이썬 내장 모듈의 강력함: 매번 최솟값이나 최댓값을 빠르게 찾아야 하는 상황에서 리스트 정렬(sort)이나 큐(deque)만으로는 성능 한계에 부딪힌다는 것을 깨달았습니다. 이런 '지속적인 최솟값 갱신' 상황에서는 우선순위 큐(heapq)가 압도적인 효율을 낸다는 사실을 확실히 체감할 수 있었습니다.
• 추가 최적화 포인트 (heapify): 현재 코드는 빈 리스트 hq에 for문을 돌며 heappush를 하고 있습니다. 이 방법도 훌륭하지만, 파이썬에서는 heapq.heapify(C)라는 함수를 쓰면 기존 리스트를 한 번에 $O(N)$의 시간 복잡도로 힙 구조로 변환할 수 있습니다. 다음번 우선순위 큐 문제에서는 이 heapify 함수를 적극 활용하여 코드를 한 줄 더 줄여보아야겠습니다.