[ 자료구조-1715 ] 카드 정렬하기(Python)

---

접근법

최소 비교 횟수를 구하기 위해서는 입력받은 묶음의 크기를 정렬한 후 작은 2개의 묶음의 크기부터 더해나가서 계산할 수 있다. 따라서 양쪽으로 입출력이 가능한 deque 자료구조를 사용하여 구현하였다.

from collections import deque

N = int(input())

tmp = []

for i in range(N):
    tmp.append(int(input()))
    
tmp.sort()
queue = deque()
for i in range(N):
    queue.append(tmp[i])

result = 0

for _ in range(1,N):
    a = queue.popleft()
    b = queue.popleft()
    result += a+b
    queue.appendleft(a+b)
    
print(result)

 

deque 자료구조 자체에는 정렬 함수가 없기 때문에, 먼저 배열로 묶음의 크기를 받은 후 sort()를 통해 정렬한 것을 다시 deque에 입력하였다. 이후 for문을 2개씩 빼고 다시 집어넣기 때문에 1부터 N까지 반복하고, popleft()를 두번하여 가장 작은 두 묶음의 크기를 더하여 result에 더한 후 그 값을 다시 appendleft()로 집어넣었다.

 

하지만 여기서 간과한 점이 더한 묶음을 다른 묶음과 비교하면서 하나로 합칠 때, deque 내에서 더한 값보다 작은 두 묶음이 존재할 경우 단순히 appendleft()를 사용한다면 틀리게 된다. 

 

따라서 입력과 동시에 정렬이 가능하도록 구현해야함을 인지하였고, 이를 위해 우선순위 큐 자료구조인 heqpq를 이용하였다.

---

정답

 

import heapq

n = int(input())
cards = []
for i in range(n):
    heapq.heappush(cards, int(input()))

result = 0

if len(cards)==1:
    print(result)

else:
    for _ in range(1,n): 
        a = heapq.heappop(cards)
        b = heapq.heappop(cards)

        result += a + b
        heapq.heappush(cards,a + b)
    
    print(result)

 

heapq는 기본적으로 minheap으로 구현된다. 따라서 입력할 때 heapq.heappush()를 통해 minheap으로 정렬시킨 후 for문을 돌면서 heapq.heappop()으로 가장 작은 두 묶음의 크기를 더하고, 더한 값을 다시 heapq.heappush()를 통해 minheap에 집어 넣음으로써 정확하게 구현할 수 있다.