BOJ-11286 절댓값 힙
https://www.acmicpc.net/problem/11286
문제 소개
절댓값 힙은 아래와 같은 연산을 지원하는 자료구조이다.
배열에 정수 $x (x != 0)$ 를 넣는다.
배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고 그 값을 배열에서 제거한다.
연산의 개수와 연산의 정보를 나타내는 정수 x가 주어진다. x가 0이 아니라면 배열에 x를 추가하고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 제거한다.
배열이 비어있는데 출력을 시도하는 경우 0을 출력한다.
문제 풀이
리스트 heap을 선언하여 heapq를 통해 최소 힙으로써 값을 추가하고 삭제하도록 하였다.
딕셔너리 형 변수인 d를 defaultdict로 선언하여 같은 절댓값을 가지는 수의 개수를 양수와 음수 따로 담아두도록 하였다.
예를 들어, d[t][0]와 d[t][1]은 각각 배열 안에 있는 절댓값이 t인 수 중 음수와 양수의 개수를 나타낸다.
배열에 값을 추가하는 경우, x가 음수인지 양수인지 판별하여 heap에 추가함과 동시에 d에도 값을 누적시킨다. 이때, 음수인 경우 d[-x]로 접근한다.
배열에서 값을 삭제하는 경우, d[heap[0]]의 값을 확인함으로써 삭제해야 할 heap[0]이 음수인지 양수인지 판별하여 d[heap[0]][0] 또는 d[heap[0]][1]을 1 감소시키고 heappop한 결과를 출력한다. 이때, 역시 음수인 경우 앞에 -를 붙여 출력한다.
힙이 비어있는 경우에는 단순히 0을 출력한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from sys import stdin
from collections import defaultdict
import heapq
input = lambda: stdin.readline().rstrip()
n = int(input())
heap = []
d = defaultdict(lambda: [0, 0])
for i in range(n):
x = int(input())
# 추가
if x != 0:
# 음수인 경우
if x < 0:
heapq.heappush(heap, -x)
d[-x][0] += 1
# 양수인 경우
else:
heapq.heappush(heap, x)
d[x][1] += 1
# 삭제
elif heap:
# 음수인 경우
if d[heap[0]][0] > 0:
d[heap[0]][0] -= 1
print(-heapq.heappop(heap))
# 양수인 경우
else:
d[heap[0]][1] -= 1
print(heapq.heappop(heap))
# 힙이 비어있는 경우
else:
print(0)