백준 11279번 최대 힙

백준 11279번 최대 힙 문제이다.

 

문제는 다음과 같다. 

 

문제를 보면 최대 힙 문제는 최소 힙 문제와 비슷하다. 

처음엔 최소 힙 문제에서 pop을 배열의 마지막을 하면 되지 않을까 생각했다.

생각한대로 구현 후 출력을 하니 생각과 많이 달랐다. heap에서의 순서는 배열의 순서를 그대로 따라가지 않았다. 

트리구조를 그대로 출력한다고 생각하면 이해가 빠르게 될 것이다. 

 

그래서 힙 자체를 변형을 시키기로 했다 최소값이 맨 앞으로 오는 구조이기 때문에 이를 바꾸어 최댓값이 맨 앞으로 오도록 만들기로 했다. 

값에 -를 붙이면 제일 큰수가 제일 작은수로 바뀌어 맨앞에 저장이 되고

출력할때만 다시 -을 붙여 출력하면 되는 것이다.

 

코드는 다음과 같다. 

import sys
import heapq

n = int(sys.stdin.readline().strip())
arr = []
for i in range(n):

    ins = sys.stdin.readline().strip()
    ins = int(ins)
    if ins == 0:
        if len(arr) == 0:
            print(0)
        else:
            print(heapq.heappop(arr)*(-1))
    else:
        heapq.heappush(arr, -ins)

 

원리만 이해하면 쉽게 구현이 가능했다.

 

성공!