절대값 힙

1. 조건

• x : 0이 아닌 정수 ( -2^31 <= x <= 2^31 )
  • x != 0 : x를 배열에 추가
  • x == 0 : 값 출력 후 제거
• N : 연산의 갯수 ( 1 <= N <= 100,000)

2. 출력

• 입력이 0인 경우 절대값이 제일 작은 값을 출력
• 만약 여러개라면 그냥 제일 작은 값을 출력
• 배열이 비어있는 경우는 0을 출력

3. 방식

• 힙을 사용하여 문제를 품
• 음수 힙과 양수 힙 2개 만듦
• 음수 힙의 경우 최대 힙의 방식을 활용하여 절댓값 기준으로 정렬되도록 함

4. 코드

# 절대값 힙

import heapq    # 파이썬 내부모듈 힙 사용
import sys

input = sys.stdin.readline  # 한 줄씩 받는 코드를 빨리 받기 위함
N = int(input())
m_heap, p_heap = [], []  # 음수 힙과 양수 힙을 따로 만듦

for _ in range(N):  # N번만큼 반복
    x = int(input())

    if x < 0:   # 음수의 경우
        heapq.heappush(m_heap, (-x, x))   # 절대값 기준이므로 양과 음의 수를 튜플 저장
    elif x > 0:  # 양수의 경우
        heapq.heappush(p_heap, x)
    elif m_heap and p_heap:  # x가 0이고 두 힙에 원소가 있는 경우
        if m_heap[0] <= p_heap[0]:  # 각 힙의 최소인 0번 원소 비교
            print(heapq.heappop(m_heap[1]))
        else:
            print(heapq.heappop(p_heap))
    elif m_heap and not p_heap:  # x가 0이고 m_heap에만 원소가 있는 경우
        print(heapq.heappop(m_heap[1]))
    elif not m_heap and p_heap:  # x가 0이고 p_heap에만 원소가 있는 경우
        print(heapq.heappop(p_heap))
    else:   # x가 0이고 두 힙이 비어있는 경우
        print(0)