[백준] 11286번 - 절댓값 힙

---

문제 분석

N의 최대범위가 100,000으로 O(nlogn) 시간 복잡도를 가진 알고리즘으로 풀 수 있다.
(1초 == 약 2000만번).
데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬이 필요하므로 우선순위 큐로 문제를 해결할 수 있다.
단, 이 문제는 절댓값 정렬이 필요하므로 우선순위 큐의 정렬 기준을 직접 정의해야 한다. (우선순위 큐의 경우 값을 대입할 경우 자동으로 오름차순으로 정렬된다.)

오류가 난 소스 코드

문제를 풀기에 앞서 우선순위 큐를 생각하지 못하고 스택으로 풀려고 한 코드이다.
아래의 코드는 시간초과가 나서 실패하였다.

# 절댓값 힙
import sys
input = sys.stdin.readline

N = int(input())
arr = []
minusArr = []
Result = []

for _ in range(N):
    value = int(input())
    if value < 0:
        arr.append(-value)
        minusArr.append(value)
    elif value > 0:
        arr.append(value)
    elif value == 0:
        if len(arr) == 0:
            print(0)
        else:
            v = arr[0]
            if -v in minusArr:
                arr.remove(v)
                minusArr.remove(-v)
                print(-v)
            else:
                arr.remove(v)
                print(v)
    arr.sort()
    minusArr.sort()

정답 소스 코드

우선순위 큐를 이용하여 튜플의 형태로 저장하여 주어진 문제를 해결하였다. 이때 튜플의 첫 번째 값이 동일할 경우 두 번째 값으로 큐가 정렬이 된다.

# 절댓값 힙
from queue import PriorityQueue
import sys
input = sys.stdin.readline

N = int(input())
q = PriorityQueue()

for i in range(N):
    value = int(input())
    if value == 0:
        if q.empty():
            print(0)
        else:
            v = q.get()
            print(v[1])
    else:
        # 튜플의 형태로 값을 저장 + 첫번째 인수값이 동일한 경우 두번째 인수값으로 정렬됨
        q.put((abs(value), value))

아래는 추가로 우선순위큐를 사용하는 방법이다.

파이썬 우선순위 큐 사용방법

1. 클래스 및 임포트 선언

from queue import PriorityQueue
queue = PriorityQueue()

만약 우선순위 큐에 사이즈 제한을 두고 싶다면 아래와 같이 선언한다.

 queue = PriorityQueue(10)

2. 원소 추가
   PriorityQueue 클래스의 put()메서드를 이용하여 우선순위 큐에 원소를 추가할 수 있다.

queue.put(4)
queue.put(8)
queue.put(12)

3. 원소 제거(=반환)
   PriorityQueue 클래스의 get()메서드를 이용하여 우선순위 큐에 원소를 제거(=반환)할 수 있다.
   또한, 우선순위 큐는 값을 오름차순으로 반환하는 특성이 있기 때문에 아래와 같은 순서로 반환한다.

que.put(4)
que.put(12)
que.put(8) 

print(queue.get()) #4
print(queue.get()) #8
print(queue.get()) #12

4. 기타 메서드
   우선순위 큐의 크기(=사이즈) 확인 => queue.qsize()
   우선순위 큐가 비어있는지 확인 => queue.empty()
   우선순위 큐가 가득 찼는지 확인 => queue.full()