11279번: 최대 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
본 코드는 파이썬으로 작성되었습니다.
우선순위 큐 라이브러리를 이용하였습니다.
파이썬의 우선순위 큐는 최소기반 힙으로만 작동하지만, put시에 음수로 반전하여 넣고,
꺼낼시에 다시 양수로 전환하여서 사용하면
최대 힙 방식으로 이용할 수 있습니다.
우선순위 큐의 시간복잡도는 n log n 이므로 우선순위를 사용하고 배열을 사용하지 않는 문제에 적합하다 생각됩니다.
from queue import PriorityQueue
import sys
N = int(input())
prQue = PriorityQueue(maxsize=N)
for _ in range(N):
i = int(sys.stdin.readline())
if i == 0:
if prQue.empty():
print(0)
else:
print(-(prQue.get()))
else:
prQue.put(-i)
728x90