https://www.acmicpc.net/problem/11286
알고리즘 분류
- 우선순위큐
문제풀이
우선 절댓값 기준으로 가장 작은 값부터 출력해야 하고, 그 값이 같을 경우 가장 작은 수를 출력해야 한다.
힙을 튜플로 구성하여 첫 번째 원소(절댓값 기준)를 기준으로 정렬해야한다.(이후 두 번째 원소 기준..)
ex)
heap=[(1, 1)]
[(1, -1), (1, 1)]
[(1, -1), (1, 1), (1, 1)]
[(1, -1), (1, 1), (1, 1), (1, 1)]
[(1, -1), (1, -1), (1, 1), (1, 1), (1, 1)]
[(1, -1), (1, -1), (1, -1), (1, 1), (1, 1), (1, 1)]
[(1, -1), (1, -1), (1, -1), (1, 1), (1, 1), (1, 1), (2, 2)]
[(1, -1), (1, -1), (1, -1), (1, 1), (1, 1), (1, 1), (2, 2), (2, -2)]
그리고나서 0일 때마다 원래값을 출력해주면 된다.
참고: https://littlefoxdiary.tistory.com/3소스코드
import heapq
import sys
input=sys.stdin.readline
n=int(input())
exp=[]
for _ in range(n):
exp.append(int(input()))
heap=[]
heapq.heapify(heap)
for i in exp:
if i!=0:
heapq.heappush(heap, (abs(i), i))
else:
try:
print(heapq.heappop(heap)[1])
except:
print(0)
