[백준] 11286 절댓값 힙 - 우선순위 큐, 힙

[ 문제링크 ]

https://www.acmicpc.net/problem/11286

 

🚩 조건

1. 연산의 개수 N(1≤N≤100,000)이 주어지면, 다음 N개의 줄에 연산에 대한 정보를 나타내는 정수 x가 주어짐.
2. x가 0이 아니라면 배열에 x라는 값을 넣는 연산임
3. x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 연산임
4. 입력되는 x는 -2^31보다 크고, 2^31보다 작음
5. 입력에서 0이 주어진 횟수만큼 답을 출력해라. 배열이 비어있는데 0이 입력되면 0을 출력해라.

 

 

🚩 접근

우선순위 큐를 사용하고 절댓값을 우선순위로 두면 되지 않을까?

 

 

🚩 시행착오

- 우선순위 큐 구현

우선순위 큐는 힙이라는 자료구조를 통해 구현할 수 있다.

힙은 완전 이진 트리 모양을 가지며, 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(=>max heap) 작다(=>min heap). 따라서 힙은 루트노드에 우선순위가 가장 높은 데이터를 위치시킨다. 힙 자료구조는 우선순위 큐를 구현하거나, 힙 정렬을 하는 데 사용된다.

[출처] https://chanhuiseok.github.io/posts/ds-4/

 

➕ 왜 우선순위 큐는 배열이나 연결리스트가 아닌, 힙으로 구현할까?

1. 배열로 구현한다면
   • 우선순위가 중간인 것이 들어가야 할 때, 뒤의 데이터 모두 한 칸씩 뒤로 밀어야 함. 최악의 경우 모든 데이터를 뒤로 밀어야 함.
   • 따라서 삭제 : O(1), 삽입 : O(n)
2. 연결리스트로 구현한다면
   • 우선순위가 중간인 것이 들어가야 할 때, 그 위치를 찾아야 함. 최악의 경우 맨 끝까지 탐색해야 함.
   • 따라서 삭제 : O(1), 삽입 : O(n)
3. 힙으로 구현한다면
   • 삽입 : 맨 끝 위치에 넣고 최소/최대 힙의 조건 위배되면 두 노드의 자리 바꿔나감
   • 삭제 : 일단 트리 구조 상에서 가장 마지막 위치인 값과 루트를 바꿔서 루트를 안전하게 제거, 이후 힙의 성질이 잘 만족될 수 있게 내부적으로 위치를 바꿈
   • 따라서 삭제 : O(log2n), 삽입 : O(log2n)
   • 참고로 "힙"을 구현할 시에는 배열을 사용하는 게 좋음

 

python에서 우선순위 큐는 PriorityQueue class로 제공되고, 이는 내부적으로 heapq 모듈을 통해 구현되어 있다. 따라서 PriorityQueue, heapq 둘 중 아무거나 사용해도 된다. (gpt 피셜로 단일 스레드 환경에서는 heapq, 멀티 스레드 환경에서는 PriorityQueue를 사용하는 걸 권장한다고 함)

from queue import PriorityQueue

# 생성 (default는 최소 힙(=오름차순 정렬))
pq = PriorityQueue()

# x라는 원소 삽입
pq.put(x)

# 원소 삭제 후 리턴
pq.get()

## 최대 힙 구현하려면
## 우선순위를 음수로 변환하여 삽입
## pq.put(-x)
## 리턴 값 사용 시 다시 양수로 변환
## print(-pq.get())

import heapq

# 생성 (default는 최소 힙(=오름차순 정렬))
hq = []

# 원소 삽입 (heap의 형태를 유지하면서 hq에 x라는 원소를 push)
heapq.heappush(hq, x)

# 원소 삭제 후 리턴 (heap의 형태를 유지하면서 hq에서 루트 노드를 반환)
heapq.heappop(heap)

# 리스트를 선형 시간내에 heap으로 변환
arr = [4, 3, 1, 2]
print(arr) # [4, 3, 1, 2]
heapq.heapify(arr)
print(arr) # [1, 2, 4, 3]

## 최대 힙 구현하려면
## 우선순위를 음수로 변환하여 삽입
## heapq.heappush(hq, -x)
## 리턴 값 사용 시 다시 양수로 변환
## print(-heapq.heappop(hq))

 

- 시간초과

python으로 문제를 풀 때 맨 첫줄 test case 개수를 입력받는 건 input()을 사용해도 무방하나, 반복문으로 여러 줄 입력받는 상황에서는 반드시 sys.stdin.readline()을 사용해야 시간초과가 발생하지 않는다!

 

 

💻 코드 (Python3)

import heapq
import sys

N = int(input())
heap = []    # 최소힙, 각 원소 : (절댓값, 실제값값)
for _ in range(N):
    x = int(sys.stdin.readline())
    if x==0:
        if not heap:
            print(0)
        else:
            min_abs = heapq.heappop(heap)
            print(min_abs[1])
    else:
        heapq.heappush(heap, (abs(x),x))

 

 

참고 )

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)

heapq — Heap queue algorithm

[Python] heapq를 이용한 최소 힙, 최대 힙