Python - [백준 1715] 카드 정렬하기 (feat. 우선순위 큐)

참조 포스트:

2025.02.24 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 힙(Heap)으로 우선순위 큐 구현하기 (feat. Lazy Deletion)

[자료구조 & 알고리즘] 힙(Heap)으로 우선순위 큐 구현하기 (feat. Lazy Deletion)

 

---

 

---

BOJ_1715_카드 정렬하기

 

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

 

첫째 줄에 최소 비교 횟수를 출력한다.

---

Checkpoint

 

이 문제를 해결하기 위해 그리디 알고리즘을 활용하여 최소한의 비교 횟수를 구해야 합니다.

또한 우선순위 큐(최소 힙) 자료구조를 활용합니다.

1. 모든 카드 묶음을 최소 힙에 삽입합니다.
2. 힙에서 가장 작은 두 개의 카드 묶음을 꺼내어 합칩니다.
3. 합친 묶음을 다시 힙에 삽입합니다.
4. 위 과정을 반복하여 최종적으로 한 개의 묶음이 남을 때까지 진행합니다.
5. 모든 과정에서 발생한 비교 횟수의 합이 정답이 됩니다.

 

문제에서 제시된 10, 30, 40 의 비교횟수에서 규칙을 발견할 수 있었습니다.

1.  (10 + 20) + (30 + 40) = 100
2.  (10 + 40) + (50 + 20) = 120

최소 비교 횟수는 1번, "(10 + 20) + (30 + 40) = 100"으로 작은 것 끼리 비교하면서 더해간다는 것을 알 수 있습니다.

또한 (10 + 20) + (30 + 40) 를 분해 해보면

       (10 + 20)   +   (10 + 20) + 40 으로 표현할 수 있죠.

여기서 2번째 규칙을 발견할 수 있습니다.

 

작은 것 2개를 더하고 이걸 다시 큐에 넣어서 다시 2개 꺼내는 것을 반복하고 있습니다.

단계	힙 상태	선택한 카드 묶음 비교	횟수 누적	남은 힙
초기	[10, 20, 40]	-	0	-
1회차	[40]	(10 + 20) → 30	30	[30, 40]
2회차	-	(30 + 40) → 70	100	[70]

---

코드 구현 (Python)

import sys
import heapq

N = int(sys.stdin.readline().strip())

if N == 0:
    print(0)
    exit()

heap = []
for _ in range(N):
    heapq.heappush(heap, int(sys.stdin.readline().strip()))

result = 0
while len(heap) > 1:  # 카드 묶음이 하나 남을 때까지 반복
    a = heapq.heappop(heap)  # 가장 작은 카드 묶음
    b = heapq.heappop(heap)  # 두 번째로 작은 카드 묶음
    sum_ab = a + b  # 합친 묶음
    result += sum_ab  # 총 비교 횟수 추가
    heapq.heappush(heap, sum_ab)  # 다시 힙에 삽입

print(result)

---

코드 설명

1️⃣ 최소 힙을 사용한 우선순위 큐 활용

• heapq 모듈을 사용하여 항상 가장 작은 두 개의 카드 묶음을 선택합니다.
• 힙은 삽입과 삭제 연산이 O(log N)이므로 전체 알고리즘은 O(N log N)의 시간 복잡도를 가집니다.

2️⃣ 비교 횟수 누적

• 두 개의 묶음을 합칠 때마다 발생하는 비교 횟수를 result에 누적합니다.
• 최종적으로 모든 카드가 하나의 묶음이 될 때까지 이 과정을 반복합니다.

3️⃣ 예외 처리 (N == 0)

• N = 0이면 카드 묶음이 없으므로 0을 출력하고 종료합니다.

---

시간 복잡도 분석

• heapq.heappop() 연산의 시간 복잡도: O(log N)
• heapq.heappush() 연산의 시간 복잡도: O(log N)
• 총 N-1번의 합병 연산이 수행됨 → O(N log N)

따라서 최적의 방법으로 문제를 해결할 수 있습니다.

---

예제 테스트

🔹 입력 예시 1

3
10
20
40

🔹 수행 과정

단계	힙 상태	선택한 카드 묶음 비교	횟수 누적	남은 힙
초기	[10, 20, 40]	-	0	-
1회차	[40]	(10 + 20) → 30	30	[30, 40]
2회차	-	(30 + 40) → 70	100	[70]

🔹 출력 예시 1

100

---

결론

✅ 핵심 정리

1. 그리디 알고리즘을 활용하여 최소한의 비교 횟수를 구해야 합니다.
2. 최소 힙(우선순위 큐)을 사용하여 항상 가장 작은 카드 묶음부터 합치는 전략을 취합니다.
3. 시간 복잡도는 O(N log N), 매우 효율적인 방식입니다.
4. 허프만 코딩과 유사한 개념으로 접근할 수 있습니다.

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.