[BOJ/python] 11286번 절댓값 힙

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

11286번: 절댓값 힙

 

 

문제 해석

 

최소 힙, 최대 힙 과 비슷한 문제로 힙을 사용하는 문제이다.

입력으로 정수를 입력받고, 이를 배열에 넣는다. 만약 입력된 수가 0이라면 배열에서 가장 작은 절대값을 가진 수를 출력한다. 만약 배열에 수가 존재하지 않으면 0을 출력한다.

---

코드

import heapq
input = __import__('sys').stdin.readline

n = int(input())
h = []

emsoo = dict()
yangsoo = dict()

for i in range(n):
    t = int(input())
    if t == 0:
        if h: 
            k = heapq.heappop(h)
            if emsoo[k] > 0:
                print(-k)
                emsoo[k] -= 1
            else:
                print(k)
                yangsoo[k] -= 1
        else: print(0)
    else:
        if abs(t) not in emsoo:
            emsoo[abs(t)] = 0
            yangsoo[abs(t)] = 0 
        if t < 0:
            emsoo[abs(t)] += 1
        elif t > 0:
            yangsoo[abs(t)] += 1

        heapq.heappush(h, abs(t))

---

문제 풀이

 

먼저 문제 제목과 같이 이는 힙을 사용하여 절대값을 넣은 뒤 이를 출력해주는 문제이다.

문제는 힙에 들어가는 값이 출력될 때 절대값으로 변환시켜 입력이 되므로 출력시 음수인지 양수인지 모른다는 것이다.

이를 해결하기위해 현재 배열 h에 존재하는 값의 음수값과 양수값을 입/출력때마다 개수를 저장해주었다.

출력시에는 음수가 먼저 출력되므로 음수의 개수가 0이 아니라면 양수의 개수를 출력하고, 개수를 -1 해주었다.

 

코드를 살펴보면 입력받은 값 t가 0이 아니라면 먼저 딕셔너리에 t가 존재하는지 확인한다.

딕셔너리가 존재하지 않는다면 해당 t의 값에 해당하는 음수, 양수 딕셔너리를 0으로 초기화한 뒤 t의 값이 음수인지 양수인지에 따라 +1 을 해주어 개수를 저장한다. 이후 배열 h에 절대값 t를 heappush 해준다.

 

만약 t의 값이 0, 즉 출력을 해야한다면 힙 h에 값이 존재하는지 먼저 확인한 후 값이 존재한다면 가장 작은 값을 heappop하여 이를 k에 저장한다. 만약 음수[k]가 존재한다면 이를 음수로 출력하고 개수를 -1하고 양수라면 이를 양수로 출력하고 개수를 -1 한다.

만약 h가 존재하지 않는다면 문제의 조건에 맞게 0을 출력하도록 하였다.

 

 

원문

https://ddingmin00.tistory.com/29

[BOJ/python] 11286번 절댓값 힙