카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 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보다 작거나 같은 양의 정수이다.
출력
첫째 줄에 최소 비교 횟수를 출력한다.
풀이
이 문제에서 요구하는 것은 어떻게 카드를 합쳐야 적은 수의 비교로 카드를 합치는지 구현하는 것이 핵심입니다. 여러장의 카드뭉치가 있을 때, 위처럼 카드 비교를 한다면 가장 적은 카드 뭉치 2개를 합쳐서 새로운 카드 뭉치를 만들고, 다시 카드 뭉치 중 가장 적은 수의 카드 뭉치를 골라서 합치는 과정을 반복한다면 최소의 비교로 카드를 모두 합칠 수 있습니다.
따라서, 우선 입력받은 카드들을 정렬하고 가장 작은 카드부터 순서대로 정렬하고, 가장 적은 카드 뭉치 두개를 고르고 다시 두개를 새롭게 고르는 과정을 우선순위 큐를 이용해서 구현해서 답을 구할 수 있습니다.
import sys
import heapq
input = sys.stdin.readline
# 카드 배열
cards = []
# 카드 뭉치의 수
n = int(input())
for _ in range(n):
# 우선순위 큐를 이용해서 카드를 정렬
heapq.heappush(cards, int(input()))
result = 0
for _ in range(n-1):
# 가장 적은 두개의 카드 뭉치 선택
first = heapq.heappop(cards)
second = heapq.heappop(cards)
total = first + second
result += total
# 합친 카드뭉치는 다시 우선순위 큐에 삽입
heapq.heappush(cards, total)
# 결과 출력
print(result)이 문제는 난이도는 높게 책정되어 있으나, 우선순위 큐를 활용하면 손쉽게 해결할 수 있는 문제였습니다.
