[정렬] 이코테 (파이썬) 카드 정렬하기 풀이

[문제]

정렬된 두 묶음의 숫자 카드가 있을 때 각 묶음의 카드의 수를 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개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하세요.

 

[입력 조건]

1. 첫째 줄에 N이 주어집니다. (1 <= N <= 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어집니다.

 

[출력 조건]

첫재 줄에 최소 비교 횟수를 출력합니다. (21억 이하)

<입력 예시>
3
10
20
40
<출력 예시>
100

 

[풀이]

import heapq

n = int(input())

heap = []
for i in range(n) :
  data = int(input())
  heapq.heappush(heap, data)

result = 0

while len(heap) != 1 :
  a = heapq.heappop(heap)
  b = heapq.heappop(heap)

  sum_value = a + b
  result += sum_value
  heapq.heappush(heap, sum_value)

print(result)

 

1. 이 문제는 우선순위 큐(heapq)를 통해 원소를 넣었다 빼는 것만으로도 정렬된 결과를 얻을 수 있다.

 

2. heap 리스트에 초기 카드 묶음을 모두 삽입한다.

 

3. while문을 통해 heap 리스트의 원소가 1개 남을 때까지 반복 수행한다.

 

4. 반복문 내에서는 가장 작은 2개의 카드 묶음 (a, b)을 꺼내 더한 값을 sum_value에 할당한다.

 

5. sum_value 값을 result에 누적해나가고 다시 heap에 삽입한다.

 

 

* 이 문제의 핵심 아이디어는 항상 가장 작은 크기의 두 카드 묶음을 합쳤을 때 최적의 해를 보장한다.

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저