백준11286 - 절댓값 힙 (heap) Python

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

어제 포스팅한 최소 힙과 비슷한 문제지만, 절댓값으로 정렬한 힙을 구현하는 문제다.

특이사항으로는 가장 작은 값이 여러 개일 경우, 가장 작은 수(절댓값이 같은 수가 둘 있다면 음수)를 먼저 출력하고 제거해야 한다.

 

내가 풀이한 방법은 다음과 같다.

- 힙 데이터 추가의 경우 ( v != 0 )

먼저 정수 절댓값으로 변환 후 절댓값 힙에 넣기 전, 해당 정수를 기록하기 위한 빈 딕셔너리를 선언했다.

이 딕셔너리는 중복도 헤아리기 위해 현재 힙에 있는 특정 정수의 수를 기록한다.

  storage = {}

  for v in arr :
    if v != 0 : 
    # 자바스크립트의 경우 단축평가를 활용한 
    # storage[v] = (storage[v] || 0) + 1 식으로 구현이 가능하나,
    # 파이썬의 경우 stroage[v]가 존재하지 않는다면 valueError를 내보내기 때문에 get 메서드를 쓴다.
    # 이때 None은 에러대신 반환되는 값
      if storage.get(v , None) : storage[v] += 1
      else : storage[v] = 1

 

다음으로는 힙을 구현한 뒤 정수를 절댓값으로 변환한 값을 힙에 추가한다.

 heapq.heappush(heap,abs(v))

 

- 출력하는 경우 (v == 0)

결괏값을 담을 result 리스트 선언한다.

먼저 heap에 요소가 없는 경우에는 0을 result에 추가해준다.

 

만약 그렇지 않을 경우는 heap에서 빼온 요소를 음수로 전환한 뒤, 

위에서 힙에 데이터 추가를 위해 사용한 딕셔너리에 해당 음수가 존재한다면 

딕셔너리에서 해당 음수를 가진 벨류값을 -1 해주고 result에 추가한다.

만약 해당 음수가 존재하지 않는다면 양수를 위와 같은 과정으로 처리한다.

if len(heap) == 0 :
        result.append(0)
      else :
        negative = -heapq.heappop(heap)
        positive = -negative
        target = negative if storage.get(negative, None) else positive
        storage[target] -= 1
        result.append(target)

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

import heapq

def solution (data) :
  data.pop(0)
  arr = list(map(int, data))
  heap = []
  result = []
  storage = {}
  
  for v in arr :
    if v != 0 : 
      if storage.get(v , None) : storage[v] += 1
      else : storage[v] = 1
      
      heapq.heappush(heap,abs(v))
    else :
      if len(heap) == 0 :
        result.append(0)
      else :
        negative = -heapq.heappop(heap)
        positive = -negative
        target = negative if storage.get(negative, None) else positive
        storage[target] -= 1
        result.append(target)
        
  print('\n'.join(map(str, result)))
  
solution(input_data)