카드 정렬하기

📌문제

정렬된 두 묶음의 숫자 카드가 있을 때 각 묶음의 카드의 수를 A,B라고 하면 보통 두 묶음을 합쳐서 하나로 만드는데에는 A+B번의 비교를 해야한다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때 최소한 몇 번의 비교가 필요한지 구하시오.

 

📌풀이

항상 가장 작은 크기의 두 카드 묶음을 합쳤을 때 최적의 해 보장

매 상황에서 가장 작은 크기의 두 카드 묶음을 꺼내어 이를 합친 뒤 다시 리스트에 삽입

우선순위 큐 사용(원소를 넣었다 빼는 것만으로 정렬된 결과 얻음)

 

📌코드

import heapq

n = int(input())

# 힙에 초기 카드 묶음을 모두 삽입
heap = []
for i in range(n):
    data = int(input())
    heapq.heappush(heap, data)

result = 0

# 힙에 원소가 1개 남을 때까지
while len(heap) != 1:
    # 가장 작은 2개의 카드 묶음 꺼내기
    one = heapq.heappop(heap)
    two = heapq.heappop(heap)
    # 카드 묶음 합쳐서 다시 힙에 삽입
    sum_value = one + two
    result += sum_value
    heapq.heappush(heap, sum_value)

print(result)

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬