[백준 11286 파이썬] 절댓값 힙 (실버1, 우선순위 큐)

알고리즘 유형 : 우선순위 큐
풀이 참고 없이 스스로 풀었나요? : △

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

SOLVE 1

import sys
import heapq
input = sys.stdin.readline

abs_heap = []

for _ in range(int(input())):
    n = int(input())
    
    if n == 0:
        if len(abs_heap) == 0:
            print(0)
        else:
            print(heapq.heappop(abs_heap)[1])
    else:
        heapq.heappush(abs_heap, (abs(n), n))

SOLVE 2

import sys
import heapq
input = sys.stdin.readline

abs_heap = []
second = {}

for _ in range(int(input())):
    n = int(input())
    
    if n == 0:
        if len(abs_heap) == 0:
            print(0)
        else:
            key = heapq.heappop(abs_heap)
            print(heapq.heappop(second[key]))
    else:
        heapq.heappush(abs_heap, abs(n))
        if abs(n) in second:
            heapq.heappush(second[abs(n)], n)
        else:
            second[abs(n)] = [n]

풀이 요약

1. heapq에 튜플을 넣는 문제이다.

2. 튜플의 첫 번째 인자로 절댓값을 넣고, 두 번째 인자로 원래 수를 넣는다. 그러면, 절댓값 기준으로 오름차순으로 리스트가 만들어진다.

3. SOLVE 2는, 문제의 조건 중 "우선순위가 같을 때, 값이 작은 것을 먼저 출력해라"를, 딕셔너리를 이용해서 직접 구현한 풀이이다.

   abs_heap에는 n의 절댓값으로만 구성된 힙을 만들어준다.

   딕셔너리에는 key는 n의 절댓값이고, value는 절댓값이 abs(n)인 모든 n으로 구성된 최소 힙이다.

   이렇게 하면, 만약 절댓값이 1인 값이 abs_heap으로부터 pop을 해서 나오면, second 딕셔너리에서 이를 키로 조회해서, 밸류인 힙에서 pop을 해준다. 밸류가 최소 힙인 리스트이기 때문에, 절댓값이 1인 수 중 작은 순으로 -1, 1이 나오게 된다.

배운 점, 어려웠던 점

• 이해가 안되는 점이 있다. 문제의 조건 중에는, 우선순위가 같으면 값이 작은 것을 먼저 출력하라는게 있다. 예를 들어, (abs(1), 1)과 (abs(-1), -1)를 이 순서대로 힙에 넣었다고 치자. 그러면 pop할때 -1이 먼저 나오고 그 뒤에 1이 나온다. 아마 튜플의 첫 번째 인자가 같으면(우선순위가 같으면), 두 번째 인자로 다시 우선순위를 매기는 모양이다. 근데 documnet를 뒤져봤을 때, 우선순위가 같은 경우에, 큐의 성질에 따라 먼저 들어온 것을 내보낸다라고 적혀있던데, 이건 안되게 되버리는 것 아닌가? 두 번째 인자로 우선순위를 또 매겨버리지 말고, 첫 번째 인자가 같은 경우에, 먼저 들어온 1을 내보내게할 수는 없는건가? 라는 의문이 들었다... priorityQueue 클래스로 해봐도 똑같다. 흠...

• 다른 사람 풀이를 참고해서, 튜플의 첫 번째 인자로 매긴 우선순위가 같은 경우, 두 번째 인자(원래의 n)를 작은 것부터 출력하라는 조건을 딕셔너리를 이용해서 직접 구현했다.