[백준/Python] (S1) 절댓값 힙 - 11286

Baekjoon Online Judge의 11286번 절댓값 힙 문제의 Python 풀이입니다.

11286번: 절댓값 힙

💻코드

import sys
import heapq

input = sys.stdin.readline  # 빠른 입력을 위한 설정

n = int(input()) 
positives = []  # 양수를 저장할 힙
negatives = []  # 음수를 저장할 힙 (저장할 때는 양수로 변환)

for _ in range(n):
    num = int(input()) 
    if num == 0:  # 입력받은 숫자가 0인 경우
        if not positives and not negatives:  # 두 힙이 모두 비어있으면 0 출력
            print(0)
        elif not negatives:  # 음수 힙이 비어있으면 양수 힙에서 하나 꺼내 출력
            print(heapq.heappop(positives))
        elif not positives:  # 양수 힙이 비어있으면 음수 힙에서 하나 꺼내 출력 (저장할 때 양수로 변환했으므로 부호 변경)
            print(-heapq.heappop(negatives))
        else:  # 두 힙 모두 비어있지 않은 경우
            if positives[0] < negatives[0]:  # 양수 힙의 최소값과 음수 힙의 최소값을 비교
                print(heapq.heappop(positives))
            else:
                print(-heapq.heappop(negatives))  # 음수 힙에서 꺼낸 후 다시 음수로 변환하여 출력
    elif num > 0:  # 입력받은 숫자가 양수인 경우 양수 힙에 추가
        heapq.heappush(positives, num)
    else:  # 입력받은 숫자가 음수인 경우 음수 힙에 추가 (저장할 때 양수로 변환)
        heapq.heappush(negatives, -num)

🧠풀이

정수를 입력받아서 0보다 큰 수는 최소 힙(min heap)에, 0보다 작은 수는 양수로 변환하여 별도의 최소 힙에 저장한다.

🤔느낀 점

heap hip heap heeap