[백준 1927] 최소 힙

문제설명

첫 줄에 연산의 수를 입력 받고, 나머지 수들을 입력 받는다.

이때 0이 들어올 때는 힙에서 가장적은 수를 출력 시킨다.

만약 힙이 없는 경우에는 0을 출력한다.

0외의 숫자가 입력되는 경우에는 힙에 넣는다. 

 

알고리즘

1. heap 선언, list 선언 
2. 총 숫자의 갯수 입력 
3. 0인지 여부 판단 후 list에 원소의 수를 세어보고 0이면 0출력, 그렇지 않는 경우 heap에서 꺼냄
4. 0이 아닌경우 heap에서 가장 작은 수 출력

 

코드

import heapq as hq
import sys

temp=[]

num= int(sys.stdin.readline())
for i in range (num):
    n= int(sys.stdin.readline())
    if n==0: #0이 들어온 경우 
        if(len(temp))==0: #원소가 없는 경우
            print("0")
        else:
            print(hq.heappop(temp)) #최소 값 출력
    else: #값 넣기
        hq.heappush(temp,n)

 

고찰

코드의 어려움 보다는 heap 개념에 대해서 충실해야 했던 문제였다.

heap을 사용하면 데이터를 정렬된 상태로 사용할 수 있다는 큰 장점이 있다.

이번 코드에서 사용한 heapq라이브러리의 경우에는 binary tree 기반의 min heap을 제공한다.

 

입력 받는 부분에 대해서 input()함수를 사용했을 때 시간초과가 발생했는데 위의 코드와 같이 변경하니

시간초과 문제를 해결할 수 있었다.