[이것이 코딩 테스트다 with Python] Chapter 14. 정렬 - 카드 정렬하기

< 카드 정렬하기 >

 

💬 문제 설명

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

....

 

입력	출력
3   10   20   40	100

💬 입력 조건

• 첫째 줄에 N ( 1 ≤ N ≤ 100,000 ) 
• N개의 줄에 걸쳐 숫자 카드 묶은의 각각의 크기( 1 ≤ 크기 ≤ 1,000 ) 

💬 출력 조건

• 최소 비교횟수 

---

✍ 문제요약

정렬된 가드 묶음을 하나로 합치려한다. 합칠 때 2개의 묶음을 합칠 수 있고, 두 카드 묶음의 카드 수의 합 만큼 비교를 해야한다. 예를 들어 A묶음 20장, B묶음 30장이면 50번 비교해야한다. 하나의 카드 뭉치로 합치는 최소 비용을 구해라.

💯 문제링크

백준1715문제와 동일하다.

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

1715번: 카드 정렬하기

---

✅  문제 풀이

• 카드 묶음들이 오름차순으로 정렬되어 있어서 1번째, 2번째 카드 묶음먼저 비교를 한다. ( 최소 비용 )
• 합쳐진 두 카드를 포함해서 다시 1번째, 2번째 카드를 비교해야한다.
• 한 번의 동작에 정렬이 계속 이루어 져야하기 때문에 heap 자료 구조를 활용했다.

heap을 활용하여  요소를 pop 하면 가장 작은 요소에 접근한다. 이는 자동으로 정렬되어 가장 작은 값을 pop 해주는 heap 자료구조의 특성이다. 또한, 트리 구조로 가장 작은 값을 탐색하여 pop 해주기 때문에 효율적이다.

• heap 에서 1번째, 2번째로 작은 카드 묶음을 pop 한다 
• 두 값을 합쳐서 나온 결과를 다시 heap 자료구조에 넣어준다.
• 새로운 값을 heap에 넣어줘도, 1번째, 2번째로 작은 카드 묶음에 접근하는데 문제가 없다.

from heapq import heappop, heappush, heapify
import sys
input = sys.stdin.readline

N = int(input())
cards = [int(input()) for _ in range(N)]
heapify(cards)              # 힙을 위한 배열로 변경

result = 0
while len(cards) > 1:       # 다 합쳐지면 종료
    a = heappop(cards)      # 하나 빼고
    b = heappop(cards)      # 하나 더 빼고
    result = result + a + b # 비교횟수 추가
    heappush(cards,a+b)     # 합한 카드뭉치 다시 리스트로 

print(result)