알고리즘/백준 문제풀이
[백준] 11286번 : 절대값 힙 (python 파이썬)
매일_공부
2022. 3. 10. 14:35
반응형
https://www.acmicpc.net/problem/11286
문제 정리 : 힙에 입력받고, 0이면 절댓값 중 최소값 출력, 최소값이 2개 이상이면 더 작은 값(음수) 출력, 배열에 아무것도 없으면 0 출력
import heapq
import sys
h = [] # 힙 생성
d = {} # 딕셔너리 생성
n = int(sys.stdin.readline())
for i in range(n):
a = int(sys.stdin.readline()) # 입력값 받기
if a == 0: # 0일 경우
if len(h) == 0: # 배열에 아무것도 없을 때
print(0) # 0출력
else:
result = heapq.heappop(h) # 절대값 최솟값 pop
if result*-1 in d: # 음수인 값이 존재할 경우
print(result*-1) # 정답 출력
if d[result*-1] == 1: # 개수가 0이 되서 삭제 되는 경우
del d[result*-1] # 딕셔너리에서 제거
else:
d[result*-1] = d[result*-1]-1
else: # 음수인 값이 없는 경우
print(result)
if d[result] == 1: #개수가 0이 되는 경우
del d[result]
else:
d[result] = d[result]-1 #딕셔너리에서 제거
else: # 0이 아닐 때
if a not in d: # 최초 입력값일 때
d[a] = 1
else: # 중복될 때
d[a] = d[a] +1 # 개수 추가
heapq.heappush(h, abs(a)) # 힙에 절대값 입력
부호를 구분하기 위해 딕셔너리 생성한다. (리스트도 가능하지만 시간초과 발생)
힙을 통해 절대값 중 최솟값을 구분해 낼 수 있다.
중복되는 값이 입력 될수 있으므로 딕셔너리의 value값으로 key값의 개수로 한다.
value값을 1씩 줄이다가 0이되면 삭제함으로서 중복되는 경우를 고려할 수 있다.
반응형