[우선순위큐/그리디] 백준 1715 카드 정렬하기 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1715번: 카드 정렬하기

 

 

 

2. 문제 풀이

 여러 개의 정렬된 카드 묶음(deck)을 하나로 합치는 데에 필요한 최소 비교횟수를 구해야 합니다. 

 

2022.02.20 - [Algorithm] - [Algorithm] 힙(heap), 최소/최대로 정렬하는 우선순위 큐

[Algorithm] 힙(heap), 최소/최대로 정렬하는 우선순위 큐

 각 카드 수가 A, B인 두 카드묶음을 합치는 데에는 A+B만큼의 비교횟수가 필요합니다. 개수가 적은 카드 묶음부터 합쳐야, 비교횟수를 최소로 할 수 있습니다. 이는 문제에도 나와있으니, 그리디 알고리즘 방법대로 쉽게 구현할 수 있습니다. 하지만 그대로 구현하면 시간초과가 납니다. 카드를 합칠 때마다 정렬하고, 첫번째와 두번째로 작은 카드 묶음을 찾아야 하기 때문입니다.

 이를 우선순위 큐를 사용하면, 효율적으로 구현할 수 있습니다.

 

 

 

3. 코드

import heapq
import sys
input = sys.stdin.readline

# 입력
n = int(input())  # 카드 묶음 수
deck = []
for _ in range(n):
    heapq.heappush(deck, int(input()))

# 우선순위 큐
if n == 1:
    print(0) # 카드뭉치가 1개이면 비교 X
else:
    res = 0  # 비교 횟수
    while len(deck) > 1:
        min1 = heapq.heappop(deck)
        min2 = heapq.heappop(deck)
        res += min1 + min2
        heapq.heappush(deck, min1+min2)
    print(res)