[백준] q1715 카드 정렬하기

문제

N개의 숫자 카드 묶음의 크기가 각각 주어진다. 두 묶음의 카드 A, B를 서로 합치려면 A+B 번의 비교를 해야 한다. 최소 비교 횟수를 구하는 프로그램을 작성하라.

어떻게 풀 것인가?

카드 묶음의 크기가 가장 낮은 값부터 묶어서 비교한다. 두 묶음의 카드를 합치고 나머지 카드 묶음과 값을 비교한다.

숫자 카드 묶음의 크기가 작을수록 우선순위가 높은 최소 힙(Min Heap)을 사용하여 구현한다.

최소 힙을 사용하면 가장 낮은 크기의 카드 묶음들끼리 비교할 수 있다.

from queue import PriorityQueue  # 클래스 임포트
que = PriorityQueue()  # 우선순위 큐 생성
n = int(input())  # N 입력받기
for i in range(n):
    que.put(int(input()))  # 우선순위 큐에 원소 추가

cnt = []
for i in range(n-1):
    s = que.get() + que.get()  # 우선순위 큐에 원소 삭제
    cnt.append(s)
    que.put(s)  # 우선순위 큐에 원소 추가

print(sum(cnt))

• 시간 복잡도

내부적으로 heap 모듈을 사용하는 PriorityQueue 클래스의 put(), get() 함수는 O(logn)의 시간 복잡도를 갖는다.