[실버 2] 백준 1927 - 최소 힙 (파이썬)

분류 : 자료구조

링크 : https://www.acmicpc.net/problem/1927

풀이

힙의 기초적인 문제이다. 사실 시간초과가 나긴했는데, sys.stdin.readline을 고려하지 못했다.

문제에서는 N이 최대 10만개이기 때문에 단순히 input()으로만으로는 당연히 시간 초과가 날 수 밖에 없다.

문제에서 N을 입력받고, 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 X가 주어진다고 한다.

X가 0이 아닌 경우에는 배열에 자연수 X를 넣고, 0이라면 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거하면 된다.

이에 적합한 자료구조는 heap이기에 아래와 같은 코드로 작성하였다.

코드

# 백준 1927 - 최소 힙

import heapq
import sys

input = sys.stdin.readline
N = int(input())
heap = []

for i in range(N) :
    x = int(input())
    if x == 0 :
        if len(heap) > 0 :
            print(heapq.heappop(heap))
        else :
            print(0)
    else :
        heapq.heappush(heap, x)