[백준] [Python] #11279 최대힙

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

11279번: 최대 힙

여러가지 뻘 짓을 하다가 애초에 이 문제는 "Heap"인 것부터 파악이 부족하다고 느꼈다.

그래서 heap구조부터 다시 공부함...

 

heap은 binary구조로 Min_heap과 Max_heap이 있다.

 

- Min_heap : root에 Min값이 옴

- Max_heap : root에 Max값이 옴

 

이 문제에서 원하는건 Max_heap인데 파이썬에 기본적으로 제공되는 heapq라이브러리는 Min_heap이다.

고로 라이브러리를 바로 사용하는 것이 아니라 새로운 장치가 필요했다.

 

import sys
import heapq
sys.stdin = open('input.txt', 'r')

n = int(input())
heap = []

for i in range(n):
    x = int(sys.stdin.readline())
    if x : #입력값이 0이 아니면 push
        heapq.heappush(heap, (-x, x)) 

    else:  #입력값이 0이 아니면 pop
        if len(heap) >= 1: 
            print(heapq.heappop(heap)[1]) 
        else: print(0) #아무것도 없으면 0 출력

 

위에서 말한 새로운 장치가 (-x, x)형식의 튜플로 heap에 push하는 부분이다

heappush(heap, value)는 heap구조를 해치지 않으면서 value를 heap에 append하는 메소드이다.

 

다만 이걸 바로 쓰면 위에 말한대로 Min_heap이 되기때문에 

(-value, value)로 쓰면 -value를 기준으로 heap을 구성해서 음수 기준의 Min, 즉 양수 기준의 Max를 구현할 수 있다.

 

그리고 마지막에 print할 때, heappop(heap)에 인덱스[1]을 붙인 이유는, 튜플 형태로 insert를 했기 때문에 원하는 value만 print하기 위해서는 0번째가 아닌 1번째 값을 print해야하기에 [1]이 붙었다.

 

참고 : https://mong9data.tistory.com/101