백준 python 기록

백준 파이썬 11279 최대 힙

작지 2021. 9. 22. 05:39

백준 링크:https://www.acmicpc.net/problem/11279

 

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가

www.acmicpc.net

 

deque를 이용해서 풀려고했지만 시간초과가 나서 검색후

 

heapq에 대한 정보를 처음 알게되었다.

https://littlefoxdiary.tistory.com/3

 

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다. 힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대

littlefoxdiary.tistory.com

 

하지만 파이썬 힙은 최소값을 구해오기 때문에

입력한 숫자를 전부 음수처리 한 후

빼올떄 다시 양수로 만들어 주었다.

import heapq
import sys

s=[]

n=int(input())
for i in range(n):
    a = int(sys.stdin.readline())
    if a == 0:
        try:
            print(-1 * heapq.heappop(s))
        except:
            print(0)
    else:
        heapq.heappush(s, (-a))