문제설명
힙을 구현하는데 기존의 힙이 아닌 절댓값을 기준으로 숫자를 정렬하는 힙을 구현하고 입력된 명령에 따른 연산결과를 출력하는 문제입니다.
연산의 종류
1. 0이 입력될 경우 힙에서 절댓값이 가장 작은 수를 출력하고 그 수를 힙에서 제거합니다.(절댓값이 같은 수가 있으면 더 작은 수를 출력)
2. 0을 제외한 다른 수가 입력된 경우 그 수를 힙에 삽입합니다.
작동 순서
1. 명령의 개수 N을 입력받습니다.
2. 입력된 수에 따라 연산을 수행합니다.
3. 힙에 수를 삽입할 때 절댓값을 기준으로 삽입을 하며 원본 값을 함께 넣어줍니다.
4. 힙에서 수를 추출할 때는 절댓값을 기준으로 추출하여서 원본 값을 출력합니다.
소스코드
import sys
import heapq
N = int(sys.stdin.readline())
heap = []
for i in range(N):
num = int(sys.stdin.readline())
if num != 0:
heapq.heappush(heap, (abs(num), num))
else:
if heap:
print(heapq.heappop(heap)[1])
else:
print(0)