문제 출처 : https://www.acmicpc.net/problem/11279

---

문제 파악

최대 힙 이라는 것을 이용하랜다.

최대 힙이란,

항상 가장 큰 값이 맨 위(root)에 있도록 유지되는 완전 이진트리 기반 자료구조다.

아무리 많은 값이 들어있어도 가장 큰 값을 O(log N) 시간 안에 꺼낼 수 있게 해주는 자료구조 이다.

---

언제 떠올리면 좋냐면,
가장 큰 값 or 가장 작은 값
을 반복적으로 꺼내야 할 때.

한 번 찾는 건 max(),min() 써버리면 되지만
수백-수천번 여러번 꺼내야 한다면? -> 힙

---

최대 힙의 규칙

부모 ≥ 자식
→ 부모 노드가 항상 자식 노드보다 크다.

항상 완전 이진트리 형태 유지
→ 왼쪽부터 빈틈없이 채운다.

이 규칙 덕분에,
힙은 가장 큰 값이 항상 root(인덱스 0)에 올라오게 된다.

---

그런데 파이썬은 최대값을 꺼내오는 최대 힙이 존재하지 않고
최소 값을 꺼내오는 '최소 힙' 라이브러리만 존재한다. heapq

그래서 최대 힙을 구현하고 싶다면 작은 트릭을 써야 한다.

---

우선 최소 힙 사용법은

• heapq.heappush(queue, n) : # queue라는 array에 최소힙의 방식으로 요소 n을 push한다.

그리고 나서

• heapq.pop(queue) 하면 queue의 최소값이 pop 됨.

import heapq

hq = []
heapq.heappush(hq, 5) 
heapq.heappush(hq, 2)
heapq.heappush(hq, 8)

min_value = heapq.heappop(hq) # 2

---

그렇다면 최대 힙은?

최소 힙을 반대로 사용할 건데

양수가 클 수록 음수는 작은 법이다.
최소 힙은 가장 작은걸 먼저 꺼내니까
'-' 마이너스 기호를 붙여서 가장 큰 값으로 만들어 꺼낸다.

• heapq.heappush(hq, -value) # 음수로 넣기
• -heapq.heappop(hq) # 꺼낼 떄 다시 양수로

heapq.heappush(hq, -5) 
heapq.heappush(hq, -2)
heapq.heappush(hq, -8)

max_value = -heapq.heappop(hq) # -8이 꺼내 지지만 -처리해주어서 8이됨.

---

그래서 이 문제는 최소힙 뒤집기를 이용한 최대힙 방법을 이용해 풀면 된다.

해답 및 코드

import heapq
import sys
input = sys.stdin.readline

N = int(input())
arr = []

for _ in range(N):
    x = int(input())

    if x == 0:
        if not arr:
            print(0)
        # 가장 큰 값 출력, 그 값 제거
        else:
            max_val = -heapq.heappop(arr)
            print(max_val)

    else:
        # 배열에 x 값 넣는 연산
        heapq.heappush(arr,-x)