백준 11286: 절댓값 힙 해설- python

백준

✏️ 문제

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

11286번: 절댓값 힙

 

✏️ 풀이

파이썬의 heapq 모듈을 이용했다. 모듈 사용에 대한 내용은 여기에서

파이썬 heapq 모듈 사용법과 응용

 

import heapq
from sys import stdin

N=int(stdin.readline())
heap=[]
for _ in range(N):
  x=int(stdin.readline())
  if x==0:
    if heap:
      print(heapq.heappop(heap)[1])
    else:
      print(0)
  else:
    heapq.heappush(heap, (abs(x),x))

IDEA : y= abs(x) 변환을 하면 최솟값 정렬이 절댓값 정렬로 바뀐다.

힙에 원소를 추가할 때 (-i, i)의 튜플형태로 넣어주면 튜플의 첫 번째 원소를 기준으로 힙을 구성하게 된다.

실제값은 튜플의 두 번째 자리에 저장되어 있으니까 [1]인덱싱을 통해서 접근해주면 된다.