❓1715번 : 카드 정렬하기
📈 문제 요약
각각 A, B장으로 구성된 두 카드 묶음을 정렬 하는 데 A+B번의 비교 횟수가 필요 한 경우 N 묶음의 카드 묶음을 정렬하는데 필요한 최소 비교 횟수를 구하면 되는 문제
🤨 접근법
예제인 각각 10, 20, 40 장의 카드 묶음을 정렬하는 경우 10장, 20장을 비교 후 정렬하여 30장을 만들고 만들어진 30장과 40장을 비교 후 정렬하여 총 100번의 비교로 최소 횟수 비교 정렬을 수행할 수 있다. 즉, 그리디하게 모든 카드팩 중 가장 작은 장 수를 가진 두 카드팩을 선택하도록 해야한다.
제일 작은 두 장을 선택한 후 합쳐서 다시 큐에 넣어줘야한다. 이 과정을 구현하기 위해서 일반적인 리스트나 큐로 접근하면 한 번의 정렬 후 제일 작은 두 카드 팩을 고를 수는 있겠지만, 합쳐서 적절한 위치에 삽입하기 어려워 매번 정렬을 해야한다.
그렇기 때문에 최소 힙을 활용한 우선순위 큐를 활용한다. 최소 힙을 활용하면 매번 카드 팩을 뽑을 때 최소 장 수를 가진 카드 팩을 뽑을 수 있고, 합쳐서 다시 힙에 넣을 때도 최소 힙을 만족하도록 삽입이 되기 때문에 별도의 정렬 과정이 필요 없다. 최소 힙은 파이썬의 내장 라이브러리인 heapq 모듈을 활용한다.
모든 카드 묶음 중 heappop으로 가장 작은 두 카드 묶음을 뽑고 각각의 수의 합을 더해 count하고, 이 순간 힙에 카드 묶음이 남아있다면 두 카드 묶음의 합을 힙에 heappush한다. 만약 힙에 카드 묶음이 남아있지 않다면 모든 카드팩이 합쳐진 것이므로 다시 힙에 넣지 않는다.
🔡 코드
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
N = int(input())
if N == 1:
print(0)
exit(0)
heap = []
for _ in range(N):
heappush(heap, int(input()))
count = 0
while heap:
weighted_card_pack = heappop(heap) + heappop(heap)
count += weighted_card_pack
if not heap:
break
else:
heappush(heap, weighted_card_pack)
print(count)하나의 카드 묶음만 존재하는 경우 이미 하나의 카드 묶음은 정렬되어 있으므로 별도의 비교과정이 필요하지 않다. 따라서 0으로 출력해주는 예외처리를 수행해주었다.
