[BOJ_Python] 11286. 절댓값 힙

문제

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

 

사용 알고리즘

우선순위 큐(heapq)

https://docs.python.org/ko/3/library/heapq.html

 

풀이

고려사항

1. 현재 절댓값이 가장 작은 숫자의 음수 여부

 

후기

1. 우선순위 큐(heapq)의 성질에 대해 자세히 알고 있었으면 더욱 쉬운 문제였다.

heapq.heappush(heap, item)

파이썬의 우선순위 큐에서 가중치 부분(item)을 튜플 형태로 제공한다면 

튜플 내의 위치 순서대로 정렬기준을 잡는다.

때문에 item 부분에 (abs(num), num)으로 절댓값의 기준과 원 숫자를 넣어주면

절댓값 기준으로 정렬하고 동일한 경우 음수를 먼저 정렬하게 되어있다.

처음에는 이 성질을 몰라 튜플로 넣어도 앞에 기준으로만 정렬되고

동일한 경우 넣은 순으로 정렬되는 줄 알고 다르게 구현하였다.

 

2. 때문에 절댓값을 정렬하는 우선순위 큐와

숫자마다 음수의 갯수를 관리하는 딕셔너리를 생성하여 관리하였다.

 

3. 이때, keypoint는 음수가 아니더라도 딕셔너리에 키를 생성해주어야 한다는 것이다.

아니면 딕셔너리에 해당 키값이 없기 때문에

음수 여부 탐색 시 keyerror가 발생한다.

 

코드

import sys
import heapq

sys.stdin = open("BOJ_11286.txt")
input = sys.stdin.readline

N = int(input())

q = []
minus_dict = {}

for _ in range(N):
    num = int(input())
    # 출력을 원할 경우
    if num == 0:
        if q:
            temp = heapq.heappop(q)
            if minus_dict[temp] > 0:
                minus_dict[temp] -= 1
                print(-temp)
            else:
                print(temp)
        else:
            print(0)

    # 수 입력 받는 경우
    else:
        heapq.heappush(q, abs(num))
        if num < 0:
            minus_dict[-num] = minus_dict.get(-num, 0) + 1
        else:
            minus_dict[num] = minus_dict.get(num, 0)

 

결과