[백준] 11286번 : 절대값 힙 (python 파이썬)

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

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이되면 삭제함으로서 중복되는 경우를 고려할 수 있다.