본문 바로가기
Problem Solving/백준

백준 1927. 최소 힙 (+파이썬 풀이)

by sohyunwriter sohyunwriter 2021. 6. 17.
728x90

Question.

 

최소 힙을 구현하는 문제이다.

 

 

 


Answer.

 

처음 파이썬으로 코딩테스트를 볼 때, heapq 모듈을 사용하는 방법을 몰라 헤맸던 기억이 난다.

 

코딩테스트에 heapq는 자주 나오니까 아래 내용을 익혀두자.

 

https://www.daleseo.com/python-heapq/

 

[파이썬] heapq 모듈 사용법

Engineering Blog by Dale Seo

www.daleseo.com

 

(내 풀이)

import heapq
import sys

input = sys.stdin.readline  ## 시간초과 방지

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

 

sol 1) 
Time Complexity O(NlogN)
Space Complexity O(N)

 

 

728x90

댓글0