1715: 카드 정렬하기

 

주어진 카드 묶음들을 비교하는데, 이 비교 횟수가 최소가 되는 값이 무엇인지 구하는 문제이다.

문제 조건에 따르면 비교할 때는 A 묶음과 B 묶음이 있을 때 합쳐서 하나로 만드는데 A+B번 비교를 해야한다.

문제 예시를 활용하면 10, 20, 40이 있을 때 10과 20을 합치면 30번의 비교가 필요하며

이렇게 될 경우 30과 40만이 남게 되고 30과 40을 다시 합치면 70번의 비교가 필요해서 총 100번의 비교를 하게 된다.

만약 순서를 바꿔서 10과 40을 먼저 합치고 비교할 경우 100번 보다 많은 횟수가 나오게 된다.

 

가장 최소 횟수로 비교하기 위해서는 정렬해서 작은 수끼리 비교하고 이 값을 누적해 나가야 한다.

누적해 나가는 값을 최솟값으로 만드는 것이 최소한의 비교 횟수가 되는데

다시 이 값을 최소로 만드는 것은 각 요소, 즉 선택하는 두 카드 묶음의 최솟값이다.

따라서 작은 묶음부터 합치고 남은 묶음과 새로 나온 묶음을 포함해서 또 가장 작은 묶음끼리 합치는 것으로 문제를 풀 수가 있다.

 

처음에는 리스트를 고려했었는데, 리스트를 사용할 경우 카드 묶음을 합칠 때마다 정렬을 하거나

삽입할 때 적절한 위치를 찾아서 삽입해야한다.

물론 파이썬 정렬은 시간복잡도가 평균적으로 O(NlogN) 이지만 정렬만 하는 것이 아니라 삽입 위치를 찾기 위해 Indexing도 해야하기 때문에 시간 초과가 발생할 가능성이 높다고 판단했다.

하지만 Heap을 사용하면 데이터를 삽입하고 삭제하는 작업이 O(logN)으로 가능하다.

따라서 Heap으로 구현된 우선순위 큐를 사용했다.

Min Heap 구조를 가지고 있는 파이썬의 heapq 라이브러리를 사용해서 입력으로 들어온 값을 push 한다.

이후 2개의 값을 pop 한 후 그 합을 다시 push 해주는 작업을 반복해서 정답을 찾을 수 있었다.

 

import sys
import heapq
 
n = int(input())
result = 0
hq = []
 
for i in range(n):
  get_card = int(sys.stdin.readline().strip())
  heapq.heappush(hq, get_card)
 
if len(hq) == 1:
  result = 0
else:
  while len(hq) > 1:
    x = heapq.heappop(hq)
    y = heapq.heappop(hq)
 
    result += x + y
    heapq.heappush(hq, x + y)
 
print(result)