[백준11279] 최대 힙

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

 

문제 해결 방법

파이썬에서는 힙 자료구조를 heapq 를 통해 제공한다. 이때 최소힙 기능만 사용할 수 있고, 최대힙 기능은 지원하지 않는다. 

최소값일 수록 우선순위를 가지고 맨 앞에 배치되니, 최대 힙을 사용하고 싶으면 값들을 넣을 때 -를 붙여 넣고, 출력할때는 -를 달아서 출력하면 최대힙 처럼 사용할 수 있다. 

 

코드 구현

 

정답 코드 

'''
# 최대 힙
'''
import heapq
import sys
input = sys.stdin.readline
n = int(input())

tmp = []
for i in range(n):
    value = int(input())
    if value !=0:
        heapq.heappush(tmp, -value)
    else:
        if not tmp:
            print(0)
        else:
            print(-heapq.heappop(tmp))

 

 

시간/공간 복잡도

log(n)

 

어려웠던 점

 

알게된 점

• heapq 모듈 사용방법