🔍 Problem

11286 절댓값 힙

우선순위 큐를 구현하는데 원소를 뽑는 기준이 절대값이 작을 수록 먼저 뽑히는 것이다. 예를들어 -1, 2가 들어있으면 -1의 절댓값이 1이므로 2보다 작고, 따라서 -1이 먼저 뽑힌다. PriorityQueue로 구현을 하면 thread-safe 체크를 하는데 이것은, 두개 이상의 스레드가 객체에 동시에 접근가능한지 체크하는 연산결과의 정합성을 보장하기 위한 하나의 과정이다. 이것을 PriorityQueue는 하고 heapq는 하지 않기 때문에 heeaq로 구현을 하였고 heapq는 non thread-safe check를 한다고 말할 수 있다. 따라서 필자는 heapq 라이브러리를 사용하여 파이썬에서 다음과 같이 구현하였다. 참고로 PriorityQueue를쓰면 thread-safe check때문에 시간초과가 뜨고 heapq는 문제가 없다. 보통 코테에서는 thread-safe check 를 요하지 않아서 heapq를 사용하면 된다.

---

📃 Input&Output

---

📒 해결 과정

가. 절대값을 기준으로 우선순위를 정하기 위해서는 -100보다 1이 먼저 출력되야한다.

나. 그렇다면 우선순위를 부여할 때, - 값은 한번더 - 를 붙여서 +로 만들어 주자 그러면 (우선순위, 값) 형식으로 힙에 들어간다고 했을 때, 힙안의 값들은 다음과 같을 것이다.

heapq = [ (100,-100), (1,1) ]

# 따라서 1이 -100보다 먼저 출력된다.

다. 그리고 만약 (1,-1), (1,1)이 들어있다면 (1,-1)부터 출력된다. 따라서 0일경우 출력하게, 혹시 비었으면 0을 출력 그리고 0이 아닐경우 힙에 넣으면된다.

---

💻 Code

# 배열에 정수 x
# 절댓값이 가장 작은 값
    # 절댓값이 같은 경우 -> 더 작은 값 출력
    

import sys, os
import heapq

# input=sys.stdin=open(os.getcwd()+"//6_Prior_Que//11286//input.txt")
input=sys.stdin

que=[]

N=int(input.readline())

for _ in range(N):
    num=int(input.readline())
    if num != 0:
        if num<0:
            heapq.heappush(que,(-1*num,num))
        else:
            heapq.heappush(que,(num,num))
            
    else:
        if len(que)!=0:
            print(heapq.heappop(que)[1])
        else:
            print(0)
    

---

🤔 느낀점

PriorityQueue로 구현을 하였을 때 thread-safe check로 인해 시간초과가 되엇다는 점이 인상깊었고 그때문에 heapq를 알게되었다.