백준 1715번 : 카드 정렬하기 (heap)

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

1. 문제점 (시간초과)

import sys
n = int(sys.stdin.readline())
cards = list(int(sys.stdin.readline()) for _ in range(n))
cards.sort()
while len(cards)>=2:
    a = cards.pop(0)
    b = cards.pop(0)
    cards.append(a+b)
    cards.sort()
print(cards)

 

 

2. 해결 (heap 사용)

import heapq

n=int(input())

heap=[]
for _ in range(n):
    data = int(input())
    heapq.heappush(heap, data)

result=0

while len(heap)!=1:
    a = heapq.heappop(heap)
    b = heapq.heappop(heap)

    sumVal = a+b
    result+=sumVal
    heapq.heappush(heap, sumVal)

print(result)

 

 

heap

• 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
• 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

 

 

 

힙 함수 활용하기

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )

 

힙 생성 & 원소 추가

heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 하기 때문에, 빈 리스트를 생성한 후 heapq의 함수를 호출할 때마다 리스트를  인자에 넘겨야 한다.

 

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap)
>>> [10, 20, 50]
print(heapq.heappop(heap))
>>> 10

 

 

최대 힙 만들기

파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙 구현을 위해서는 트릭이 필요하다.

IDEA: y = -x 변환을 하면 최솟값 정렬이 최댓값 정렬로 바뀐다.

힙에 원소를 추가할 때 -item 의 형태로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성하게 된다.  이때 원소 값의 부호를 바꿨기 때문에, 최소 힙으로 구현된 heapq 모듈을 최대 힙 구현에 활용하게 되는 것이다.