[BOJ/백준] 1715 - 카드 정렬하기 (Python)

문제

문제링크

매우 많은 숫자 카드 묶음이 있을 때, 이들 중 두 묶음씩 골라 서로 합쳐나간다.

이때 최소 몇 번의 비교가 필요한가?

 

풀이

우선순위 큐를 사용하는 문제이다.

heapq는 파이썬의 힙 자료구조로 기본적으로 최소 힙을 구현한다.

haepify로 카드묶음을 최소 힙으로 변환한다.

heappop으로 카드 묶음 중 가장 작은 두 원소를 꺼내 합친다. 이 과정을 두 번씩 한다.

이 둘을 합쳐 비교 횟수에 더하고 4개의 원소가 빠진(2번의 과정이었으므로) card에 합을 추가한다.

마지막 비교까지(card 원소가 1개일 때) 위 과정을 반복한다.

 

코드

import sys
input=sys.stdin.readline
import heapq

n=int(input())
card=[int(input()) for _ in range(n)]

heapq.heapify(card) #최소 힙으로 변환
compare=0
while len(card)>1:
    a=heapq.heappop(card) #최소 힙에서 가장 작은 원소 두 원소 꺼내 합치기
    b=heapq.heappop(card)
    compare+=(a+b)
    heapq.heappush(card, a+b) #힙에 원소 추가
print(compare)