[백준/Python] 11279 : 최대 힙

 

 

 

저번에 파이썬의 heapq 라이브러리를 사용하여 최소 힙을 구현해보았었는데, 이번 문제와 같이 최대 힙의 경우에는 heapq 가 최대 힙 구현 기능을 제공하지 않는다는 특징이 있다.

 

참고로 heapq 의 heappush(heap, item) 메소드는 힙 불변성을 유지하면서 item 값을 heap으로 삽입해주고, heappop(heap) 메소드는 힙 불변성을 유지하면서 heap에서 가장 작은 항목들을 pop하고 반환해주는 메소드였다.

 

그러나 최대힙의 경우 이를 적절히 변형해서 구현할 수 있는데, 부호를 변경하는 방법을 사용해서 구현할 수 있다!

 

import heapq
heap = []
values = [1, 5, 4, 2, 3]

for v in values:
    heapq.heappush(heap, -v) # [-5, -3, -4, -1, -2] 이 됨

for i in range(5):
    print(-heapq.heappop(heap)) # 5, 4, 3, 2, 1 을 차례대로 출력

 

간단한 예제를 작성해보았다.

 

기존의 heappush(heap, value)를 사용하면 값들이 최소 힙 순서인 [1, 2, 4, 5, 3]으로 자동 정렬된다.

 

그러나 이를 최대 힙으로 바꾸기 위해 삽입하는 value값을 음수로 세팅하여 실행하면 값 자체로는 최소힙이 구현되지만, 사실상 절댓값으로 따지면 최대힙이 구현된 상태를 만들어낼 수 있다. [-5, -3, -4, -1, -2]

 

이를 다음 반복문에서 heappop(heap)으로 원소 추출 시에도 일단 음수 기준 가장 값이 작은 값을 pop한 뒤, print하기 전에 메소드 앞에 음수 부호(-)를 붙여서 이전에 음수로 변환되었던 숫자들을 다시 양수로 되돌린 후에 출력을 진행하게 되면 최대 양수값이 출력됨으로서 최대힙을 구현할 수 있게 된다!

 

같은 원리를 이용하여 해당 문제를 다음과 같이 쉽게 풀 수 있었다.

 

import sys
import heapq
N = int(input())
heap = []

for _ in range(N):
    calc = list(map(int, sys.stdin.readline().split()))
    for num in calc:
        if num == 0:
            if heap: print(-heapq.heappop(heap))
            else: print(0)
        else:
            heapq.heappush(heap, -num)

 

입력 문자열이 0일때는 heapq를 역으로 이용하기 위해 음수 부호를 붙여 가장 큰 값을 출력하도록 하였다.

 

그리고 입력 값이 자연수여서 값을 삽입할 때에는 두 번째 인자에 음수 부호를 -num과 같이 붙여서 음수로서 삽입되도록 구현하였다.