(Python) - BOJ(11286번) : 절댓값 힙

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

11286번: 절댓값 힙

---

• 해설 : 

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

 

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

 

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

 

 

---

• 풀이 :

heapq를 사용하여 해결할 수 있다. 여기서 heeaq의 첫 번째 인자를 abs(값)으로 취해주면 되는데 이 때, 절댓값이 같은경우를 처리해주기 위해 원래값도 넣어주어야 한다.

 

 

 

---

• 소스코드 : 

 

import sys
import heapq as hq
input = sys.stdin.readline
 
if __name__ == "__main__":
    N = int(input())
    heep = []
    for _ in range(N):
        value = int(input())
        if value == 0:
            if heep:
                print(hq.heappop(heep)[1])
            else:
                print(0)
        else:
            hq.heappush(heep,[abs(value), value])