절댓값 힙_백준11286

 

<문제>

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

 

 

<풀이>

import sys
import heapq

input = sys.stdin.readline
N = int(input())
heap = []
m_dict = {}

for _ in range(N):
    x = int(input())

    if x != 0: # push
        if x > 0: # x가 양수일 경우
            heapq.heappush(heap, x)
        else: # x가 음수일 경우
            heapq.heappush(heap, -x)
            if -x in m_dict:
                m_dict[-x] += 1
            else:
                m_dict[-x] = 1
    else: # pop
        if len(heap) == 0: # 배열이 비어있는 경우
            print(0)
        else: # 비어있지 않은 경우
            min = heapq.heappop(heap)
            if min in m_dict: # 미리 저장해둔 마이너스 딕셔너리에 min값에 해당하는 값이 존재하면
                print(-min)
                m_dict[min] -= 1
                if m_dict[min] == 0: # 하나 뽑아서 마이너스 딕셔너리에 해당 키의 값이 0이 되었을때
                    del m_dict[min]
            else: 
                print(min)

 

- 절댓값이라는 조건 때문에 자료구조를 2개 써야 하는 문제

- 위 풀이는 최소힙 + 딕셔너리

- 최소힙에는 양수 정수만 저장해놓고, 딕셔너리에 마이너스로 저장한 값들의 갯수를 모아둔다

- 음수를 저장해야 하는 경우 딕셔너리에 해당 음수의 절댓값을 키로, 값을 +1 해준다

- x = 0에 의해 반대로 숫자들을 뽑아낼 때는 딕셔너리를 검사해서 해당 숫자로 카운트된 적이 있는지 살핀다

- 카운트된 적이 있다면 음수로 변환해주고 딕셔너리에서 -1 해주는데

- 0보다 작아진 값이 카운트값에 들어갈 수 있으니까 0이 되면 아예 delete 해준다

 

 

<다른 풀이>

import sys
# sys.stdin = open('data.txt', 'r')
input = sys.stdin.readline
from heapq import heappop, heappush


def main():
    
    plus_heap = []
    minus_heap = []
    _, *nums = map(int, sys.stdin.buffer.read().split())
    
    for x in nums:
        if x > 0:
            heappush(plus_heap, x)
        elif x < 0:
            heappush(minus_heap, -x)
        else:
            if plus_heap and minus_heap:
                if plus_heap[0] >= minus_heap[0]:
                    temp = -heappop(minus_heap)
                else:
                    temp = heappop(plus_heap)
            elif plus_heap:
                temp = heappop(plus_heap)
            elif minus_heap:
                temp = -heappop(minus_heap)
            else:
                temp = 0
            sys.stdout.write(str(temp) + '\n')


if __name__ == '__main__':
    main()

 

- 최소힙 2개를 쓴 풀이

- 최소힙이지만 음수, 양수를 각각 다른 곳에 저장해두어서 첫번째 값(가장 작은 값)끼리 비교

- 반환할 값을 temp로 저장해놓고 마지막에 반환하는 것도 괜찮아 보인다