[백준알고리즘/11279번/파이썬] 최대 힙

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

11279번: 최대 힙

문제: 최대 힙을 통해서 입력된 값이 0일 경우에는 힙 안의 최대 값을 출력한 후 해당 값을 제거, 자연수일 경우 배열에 자연수를 넣는 연산을 수행하는 프로그램 작성하기

 

풀이 방법: 최소 힙인 heapq을 priority를 설정하여 최대 힙처럼 활용하기

 

풀이 설명:

 

최소 힙인 heapq를 활용하는데, 값의 입력을 (priority(-value),value) 형태로 입력하여 최대 힙으로 활용하여 문제를 해결하였다.

 

풀어서 설명하자면,

heapq.heappush(1)

heapq.heappush(2) 를 수행하게 되면, heapq는 [1,2]가 되어

heapq.heappop(heap)을 수행하면 1,2 순서대로 나오게 된다.

 

하지만 push 할 때, (-1,1) ,(-2,2) 형태로 입력하고자하는 value의 음수 값을 priority 역할로 값을 넣어 입력하게되면 

heapq는  [(-2,2),(-1,1)] 된다. 

 

여기서, heapq.heappop(heap)을 수행하게 되면 최대 값을 가지고 있는 (-2,2) 부터 나오게 된다.

 

이 원리를 통해 pop을 수행할 경우 최대 값을 담은 요소부터 나오게 되는 최대 힙을 만들어 활용하였다.

 

 

풀이 코드:

import sys
import heapq

n = int(sys.stdin.readline())
heap =[]
for _ in range(n):
    val = int(sys.stdin.readline())
    if(val == 0):
        if(len(heap) == 0):
            print(0)
        else:
            print(heapq.heappop(heap)[1])
    else:
        heapq.heappush(heap,(-val,val))