알고리즘💻/우선순위큐&다익스트라
BOJ 11279번: 최대 힙
호프
2021. 2. 15. 17:36
11279번: 최대 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가
www.acmicpc.net
아이디어:
문제 이름 그대로 최대 힙을 구현하면 된다.
그런데 파이썬에서 제공하는 heapq 모듈은 최소힙이므로, 최대힙을 구현하려면 튜플을 이용하여 - 추가하는 첫번째 원소가 우선순위가 되고 이걸 기준으로 최소힙으로 정렬되므로 - 구현해야 한다. 출력할 때는 [1]번 원소를 출력하면 된다.
#11279번 최대 힙
import sys, heapq
N = int(sys.stdin.readline())
h = []
for _ in range(N):
x = int(sys.stdin.readline())
if (x==0):
if (len(h)==0): #배열이 비어있는 경우
print(0)
else:
print(heapq.heappop(h)[1])
else:
heapq.heappush(h,(-x,x)) #-x를 우선순위로 하여 최대힙 구현