(파이썬) 백준 11286번 "절댓값 힙"

---

# 문제상황 1

 

 

시간 제한이 짧으므로 시간 단축을 위한 장치가 필요합니다.

 

 

 

 

---

# 해결 1

import sys

input = sys.stdin.readline

위와 같이 sys를 import하고 sys.stdin.readline() 함수를 이용해 사용자 입력을 받으면 시간을 단축할 수 있습니다. 매번 sys.stdin.readline()을 타이핑하기는 귀찮으니 input에 sys.stdin.readline을 할당하고 평소처럼 input을 사용합시다.

 

 

 

 

---

# 문제상황 2

 

간단하게 생각해서 이 문제는 절댓값을 비교해서 가장 작은 값을 꺼내야 하므로, 우선순위 큐에 절댓값을 저장한다는 아이디어를 떠올릴 수 있습니다. 하지만 최종적으로 출력해야하는 값은 원본 값이므로 원본 값도 함께 알아야 합니다.

 

우선순위 큐에 절댓값과 원본값을 동시에 저장할 수 있을까요?

 

 

 

 

---

# 해결 2

 

절댓값과 원본값을 튜플 또는 리스트로 묶어서 우선순위 큐에 저장하면 됩니다.

heapq.heappush(hq, (abs(x), x))

 

이렇게 우선순위 큐에 넣는 자료형이 단일 값이 아닌 선형 자료구조라면, 기본적으로는 맨 앞의 요소부터 우선적으로 정렬합니다. 혹시나 맨 앞의 요소의 값이 동일하다면, 두 번째 요소를 기준으로 자동 정렬됩니다.

 

 

 

 

---

# 답

import sys, heapq

input = sys.stdin.readline
hq = []
for i in range(int(input())):
    x = int(input())
    if not x:
        print(heapq.heappop(hq)[1] if len(hq) else 0)
    else:
        heapq.heappush(hq, (abs(x), x))