[파이썬/python] 백준 - 1715 카드 정렬하기

문제

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

---

문제 설명

1. 정렬된 두 묶음의 숫자 카드가 있다.
2. 각 묶음의 카드 수 A, B를 합쳐서 하나로 만드는 데 A + B번의 비교를 해야 한다.
3. 매우 많은 숫자 카드 묶음이 존재할 때 최소의 비교 횟수를 구한다.

 

---

풀이

[10,20,40]의 카드 묶음이 존재한다고 가정하자.

먼저 10,40을 합치고, 합친 묶음 50을 20과 합친다면, 총 120번의 비교가 필요하다. 

하지만 10,20을 합치고, 합친 묶음 30과 40을 합친다면, 총 100번의 비교가 필요하다.

같은 묶음을 합쳤는데 왜 다른 횟수가 나오게 될까?

 

1번 방법은 먼저 10과 40을 합친다. 그리고 합쳐진 50(10 + 40)장 묶음을 20과 합친다. 이를 식으로 나타내보면(10 + 40) + ((10 + 40) + 20)으로 정리할 수 있다.

2번 방법는 먼저 10과 20을 합친다. 그리고 합쳐진 50(10 + 20)장 묶음을 40과 합친다. 이를 식으로 나타내보면  (10 + 20) + ((10 + 20) + 40)으로 정리할 수 있다.

 

위 예제 풀이를 들여다보면 그 이유를 찾을 수 있다.

1번 방법은 40이 2번 중복되어서 계산되고, 2번 방법은 20이 중복되어서 계산된다.

즉, 처음부터 많은 장 수의 묶음을 정렬하게 되면 횟수를 거듭할수록 비교 횟수가 비약적으로 상승하게 된다. 따라서 적은 장 수의 카드 묶음부터 순차적으로 정렬한다면, 최소 횟수가 될 것이다. 따라서 최소 힙을 통해 장 수가 가장 적은 묶음을 계속해서 꺼내 연산을 진행했다.

1. hq에 최초 카드 묶음을 전부 삽입한다.
2. hq의 크기가 1이 될 때까지 계속해서 카드 묶음을 합친다.
   1. 현재 가장 작은 크기의 두 묶음을 최소 힙에서 꺼내 합 연산한다.
   2. 총 연산 횟수에 더한 후, 다시 최소 힙에 넣는다.
3. 최종 연산 횟수를 출력한다.

---

코드

import sys
import heapq
input = sys.stdin.readline

n = int(input())
hq = [int(input()) for _ in range(n)]
heapq.heapify(hq)

res = 0
while len(hq) > 1:
    cnt = heapq.heappop(hq) + heapq.heappop(hq)
    res += cnt
    heapq.heappush(hq, cnt)

print(res)

 

---

시간복잡도

• 최소 힙의 push, pop연산은 $O(logN)$의 시간복잡도를 가진다.
• 최악의 경우 $N = 10^5$이다. 따라서 약 $O(log{10^5})$의 시간복잡도가 소요된다.