[baekjoon] 백준 11286번 : 절대값 힙 (by python 파이썬) heapq(튜플)

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

 

정답 code

#절대값 힙
import sys
import heapq
input = sys.stdin.readline

heap = []

n = int(input())
for i in range(n):
    x = int(input())
    
    if x == 0:
        if not heap:
            print(0)
        else:
            print(heapq.heappop(heap)[1])
    
    else:
        heapq.heappush(heap,(abs(x),x))

 

solution

처음엔 힙큐에 튜플형태로 넣는 방법을 생각하지 못하고 힙큐를 두개 만들으려 하였다.

절대값으로 정렬된 힙과 최솟값으로 정렬된 힙을 만들어 찾으려하였는데 두 힙을 동기화 해야되고 과정이 복잡해 다른방법을 생각하다 튜플 형태로 풀게되었다.

 

heappush할때 (절대값,원형) 형태로 넣으면 heap이 최소 값을 처리할때 절대값의 최소를 우선적으로 처리하고 절대값의 최소가 같으면 원형이 작은 수를 최소값으로 넣게 된다.

 

이를 이용해 heqppush하고 출력시 [1]번인덱스에 원형 수를 출력해주면 원하는 값을 얻게 된다.