Python3/백준 알고리즘
2022.02.11 [백준] (python 파이썬) 절댓값 힙
ian's coding
2022. 2. 11. 21:29
728x90
반응형
https://www.acmicpc.net/problem/11286
11286번: 절댓값 힙
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net


풀이
이 문제를 해결하기 위해 두개의 힙리스트를 만들었다. heap은 모든 수를 절대값으로 저장,
neg_heap은 음수 값을 절대 값으로 저장했다. 그래서 n=0일 때, neg_heap의 길이가 0이 아니고
heap[0]와 neg_heap[0]의 값이 같으면 heap의 최소값이 음수를 절대값으로 저장한 것이기 때문에
heapq.heappop의 값에 -1을 곱해 출력하고 neg_heap의 최소 값을 제거했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
import sys, heapq
heap=[]
neg_heap=[]
for _ in range(int(sys.stdin.readline())):
n=int(sys.stdin.readline())
if n<0:
heapq.heappush(neg_heap,abs(n))
if n==0:
if len(heap)==0:
print(0)
else:
if len(neg_heap)!=0 and neg_heap[0]==heap[0]:
print(heapq.heappop(heap)*-1)
heapq.heappop(neg_heap)
else:
print(heapq.heappop(heap))
else:
heapq.heappush(heap,abs(n))
|
cs |
728x90
반응형