[Baekjoon]백준 11286 절댓값 힙(실버 1) - Python

문제설명

예제

문제를 살펴보면 이번에는 절댓값을 기준으로 최소힙을 구현하여야한다

그렇다고 해서 절댓값으로 바꾸어 힙에 넣거나, 출력하는 것이 아니기 때문에 기존의 값도 저장되어야한다

그래서 최소힙과  최대힙을 둘 다 만들어 이를 저장하고 결과를 출력하는 방법을 선택하였다

 

음수의 경우 부호를 양수로 바꾸어 최소힙으로 구현하되, 값을 넣고 출력할 때 부호만 바꾸어주면

절댓값으로 값을 비교할 수 있게 된다 양수의 경우 그대로 최소힙으로 구현하면 된다

해당 방법을 사용하면 max_heap에는 음수의 절댓값이 작은 값부터 저장되어있을 것이고, 

min_heap에는 양수가 작은 값부터 저장되어있을것이다 

그렇다면 절댓값을 비교할 때에는 min_heap[0]과 max_heap[0]을 비교하면 된다

import sys
import heapq
input = sys.stdin.readline

cnt = int(input())
max_heap = [] # 음수 절댓값 저장
min_heap = [] # 양수 절댓값 저장
for _ in range(cnt):
    x = int(input())
    if x == 0: # 결과값 출력
        if min_heap:
            if max_heap: # 최소힙과 최대힙이 둘 다 존재할 때
                if min_heap[0] < max_heap[0]:
                    print(heapq.heappop(min_heap))
                else:
                    print(-heapq.heappop(max_heap))
            else: # 최소힙만 존재할 때 
                print(heapq.heappop(min_heap))
        elif max_heap:
            print(-heapq.heappop(max_heap))
        else:
            print(0)
    elif x > 0: # 양수일때
        heapq.heappush(min_heap, x)
    elif x < 0: # 음수일때
        heapq.heappush(max_heap, -x)