문제
절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.
- 배열에 정수 x (x ≠ 0)를 넣는다.
- 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
입력
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.
출력
입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
예제 입력 1
18
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0
예제 출력 1
-1
1
0
-1
-1
1
1
-2
2
0
문제 해결 과정
어제 최소 힙, 최대 힙과 관련된 문제를 풀었기 때문에 자신감 있게 문제 풀이에 돌입했다.
일단 문제는 절대값이 작은 것을 찾고 그에 맞는 값을 출력해내는 것인데, 처음에 딕셔너리를 사용해야하나? 하고 생각했다.
하지만 힙을 사용하기 위해선 리스트를 사용해야 했기에 다른 방법을 생각했다.
내가 생각한 방법은 절대값이라는 것이 사실상 '-' 부호를 없애는 것이기 때문에 0보다 작은 값이 들어온다면 - 부호를 떼고 힙에 저장을 하고 그럴 때마다 카운트를 해서 - 값이 얼마나 들어왔는지 계산하는 것이다.
그러고 출력할 때는 카운트한 수 만큼 다시 -를 붙여서 내보내는 것이다.
그래서 내가 처음 짠 코드는 다음과 같다.
import heapq as hq
import sys
N = int(input())
l = []
cnt = {}
for _ in range(N) :
x = int(sys.stdin.readline())
if x != 0 :
if x < 0 :
hq.heappush(l, -x)
cnt += 1
else :
hq.heappush(l, x)
else :
leng = len(l)
if leng != 0 :
if cnt > 0 :
print(-hq.heappop(l))
cnt -= 1
else :
print(hq.heappop(l))
else :
print(0)하지만 이 코드는 주어진 예시 입력에서부터 오류를 찾을 수 있었다.
1 / 1 / -1 / -1 / -2 / 2
가 들어왔을 때, cnt 값을 3이 된다.
하지만 0이 3번 이상 들어오게 되면, 출력 -1 / -1 / -1이 되어 cnt 값을 모두 소진해버리고 만다. 여기서 오류가 생긴다.
그래서 고민 끝에 블로그를 찾다.
리스트에 튜플이 들어갈 수 있다는 사실을 알게 되었다.
정확히 말하자면, 까먹고 있었다.
튜플의 0번째 index에 절대값을 넣고, 1번째 index에 원래 값을 넣으면 최소 힙으로 판단할 수 있고 출력도 원래 값을 출력할 수 있다.
따라서 전체 코드는 다음과 같다.
import heapq as hq
import sys
N = int(input())
l = []
for _ in range(N) :
x = int(sys.stdin.readline())
if x != 0 :
hq.heappush(l, (abs(x), x))
else :
if l :
print(hq.heappop(l)[1])
else :
print(0)참고 블로그
