문제

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

• 최대 힙을 구현하는 문제

풀이

input이 크기 때문에 시간 초과가 발생하지 않도록 하기 위해서 sys.stdin.readline()을 활용하여 input을 처리했다. 파이썬에서 제공하는 우선순위 큐를 활용하여 최대 힙을 구현했다. 파이썬의 우선순위 큐는 기본적으로 최소 힙 방식으로 동작하기 때문에 부호를 반대로 하여 값을 저장하고 최대 힙처럼 동작하도록 하여 문제를 풀었다.

import sys
import heapq
input = sys.stdin.readline

# 최대 최솟값 -> 힙 사용
# 기존의 우선순위 큐는 최소 힙 구조임
# - 기호를 사용하면 최대 힙 구조로 활용할 수 있음
# 배열 요소의 최댓값 또는 최솟값을 구해야하는 문제에서 활용하기 좋다

N = int(input())
heap = []
for _ in range(N):
    x = int(input())
    # x is not 0
    if x:
        heapq.heappush(heap, -x)
    else:
        if heap:
            print(-heapq.heappop(heap))
        else:
            print(0)