[Algorithm] 백준 11286 : 절댓값 힙

문제
https://www.acmicpc.net/problem/11286
풀이
https://github.com/nowChae/algorithm/blob/master/%EB%B0%B1%EC%A4%80/Silver/11286.%E2%80%85%EC%A0%88%EB%8C%93%EA%B0%92%E2%80%85%ED%9E%99/%EC%A0%88%EB%8C%93%EA%B0%92%E2%80%85%ED%9E%99.py

백준 최대 힙, 최소 힙 문제와 같이 heapq 모듈을 사용하여 문제를 풀어주었다. 이번 문제는 절댓값이 가장 작은 값을 출력하고, 절댓값이 가장 작은 값이 여러 개 일 때는 실제로 가장 작은 수를 출력하는 문제였다. 따라서 입력된 값 i가 음수 일 경우에는 heapq.heappush(heap, (-i, i)) 를 사용하고, i가 양수일 경우에는 heapq.heappush(heap, (i, i))를 사용하였다.

heap 리스트에 (-i, i) 또는 (i, i) 튜플이 들어가면 0번 인덱스를 기준으로 정렬되고 0번 인덱스 값이 같을 경우에는 1번 인덱스 값을 기준으로 정렬된다. 따라서 (1, 1) (1, -1)이 들어갈 경우 가장 작은 값은 (1, -1)이 된다.

< 풀이 코드 >

import sys
import heapq
input = sys.stdin.readline

N = int(input())
heap = []

for _ in range(N):
  i = int(input())

  if i == 0:
    if len(heap) == 0:
      print(0)
    else:
      print(heapq.heappop(heap)[1])
  else:
    if i > 0:
      heapq.heappush(heap, (i,i))
    else:
      heapq.heappush(heap, (-i,i))