[백준 파이썬 11286] 절댓값 힙

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

11286번: 절댓값 힙

import heapq
import sys

input = sys.stdin.readline

n = int(input())
pq = [] # 우선순위 힙

for _ in range(n):
    x = int(input())
    if x == 0: # 0을 입력 받으면
        # 힙이 비어있으면 0을 출력, 아니면 최소 절댓값 중에서 최솟값 출력 
        print(heapq.heappop(pq)[1] if pq else 0)
    else:
        # (절댓값, 원래값) 튜플로 넣어서 절댓값으로 1차 비교 후 원래값 중 최솟값으로 비교하도록 함 
        heapq.heappush(pq, (abs(x), x))

 

유데미에서 컴공선배 알고리즘 캠프 강의를 듣고 있는데 힙 이라는 걸 처음봤다;; 힙은 최댓값(or 최솟값)을 빠르게 찾아내기 위해서 고안된 완전이진트리를 기본으로 한 자료구조 라고 한다. 트리구조는 알고 있어서 이후의 이해는 쉬웠다. 

 

파이썬은 기본적으로 최소힙이고, 최대힙으로 만드려면 값을 넣을 때 -를 붙여주고 다시 꺼낼 때 또 -를 붙여주면 된다. 

 

heappush (삽입)의 시간복잡도는 O(logN) 이고, heappop (출력/삭제)도 O(logN) 이다. 

 

일단 힙 쓸 때의 코드 템플릿은 

import heapq as hq

q = []
item = 3

hq.heappush(q, item)
item = hq.heappop(q)

이렇게 쓴다.