[Python] 백준11286 절댓값 힙

22 Jan 2023 in Study on Algorithm

백준11286 절댓값 힙 링크

문제

예제 입력

---

코드

import sys
import heapq

n = int(input())
positive_arr = []
negative_arr = []
for _ in range(n):
    x = int(sys.stdin.readline())
    if x == 0: # 제거
        if positive_arr and negative_arr:
            if positive_arr[0] >= negative_arr[0]:
                print(-heapq.heappop(negative_arr))
            else :
                print(heapq.heappop(positive_arr))

        elif positive_arr and not negative_arr:
            print(heapq.heappop(positive_arr))

        elif not positive_arr and negative_arr:
            print(-heapq.heappop(negative_arr))

        else :
            print(0)

    else : # 삽입
        if x > 0 :
            heapq.heappush(positive_arr, x)
        else :
            heapq.heappush(negative_arr, -x)

설명

파이썬을 통해서 사용자로부터 입력받아 자료형 list를 사용하여 절댓값 힙를 구현했습니다.

---

정리

for _ in range(N):
    temp = int(sys.stdin.readline())
    if temp == 0 :  # 삭제
        if heap :   # 힙이 존재하면 출력 [0] = 순위, [1] = 값
            print(heapq.heappop(heap)[1])
        else :
            print(0)
    else :  # 삽입
        heapq.heappush(heap, (abs(temp), temp))

그 외에도 값을 페어로 (순위, 값)으로 저장하여 구할 수 있습니다.

---

결과