백준 11279 - 최대 힙

문제

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

 

 

풀이

우선순위 큐를 이용해 O(n * logⁿ) 시간복잡도로 해결한다

 

파이썬에서는 heapq 라이브러리를 이용해 최소 힙으로 우선순위 큐를 사용할 수 있다

문제에서 최대 값을 찾아야하므로 숫자를 저장할 때 음수로 바꿔서 저장하면 최대 힙처럼 사용할 수 있다

 

 

코드

python

import heapq
import sys
 
n = int(input())
 
heap = []
 
for _ in range(n):
    x = int(sys.stdin.readline())
    if x == 0:
        if heap:
            print(-heapq.heappop(heap))
        else:
            print(0)
    else:
        heapq.heappush(heap, -x)