백준 11286번 절댓값 힙

이전 문제인 최소 힙과 최대 힙하고 비슷한 문제이지만 이 문제에서는 절대값으로 저장을 한다 따라서 숫자를 받을때 음수와 양수를 어떻게 처리하는지가 중요하다

 

절대값으로 숫자를 받아서 정리하지만 출력할 때는 음수와 양수를 구분해서 출력해야한다 그래서 처음에 다른 리스트(원본 저장)를 추가로 만들어서 그곳에 입력 받은 원소를 저장하고 힙에는 절대값으로 저장한다

이제 출력을 할때 pop해서 -를 붙힌뒤에 원본 저장 리스트에 있는지 찾는다 없다면 양수이므로 양수로 출력하고 있으면 해당값을 음수로 출력한다

 

 

문제 해결 -1

import sys, heapq

abs_heap = []
heap = []

n = int(sys.stdin.readline().strip())

for i in range(0,n):
    x = int(sys.stdin.readline().strip())
    
    if x == 0:
        if len(abs_heap) == 0:
            print(0)
        else:
            if  -abs_heap[0] in heap:
                heap.remove(-abs_heap[0])
                print(-(heapq.heappop(abs_heap)))
            else:
                print((heapq.heappop(abs_heap)))
    else:
        heapq.heappush(abs_heap,abs(x))
        heap.append(x)

 

python3로 답을 제출하면 시간 초과가 나오고 pypy3로 제출하면 정상적으로 완료 되지만 시간이 오래 걸린다

 

 

문제 해결 -2

import sys, heapq

n = int(sys.stdin.readline().strip())
abs_heap = []

for i in range(0,n):
    x = int(sys.stdin.readline().strip())
    if x == 0:
        if len(abs_heap) == 0:
            print(0)
        else:
            print(heapq.heappop(abs_heap)[1])
    else:
        heapq.heappush(abs_heap, [abs(x), x])

힙에 추가 할 때 안에 리스트형식으로 (절대값 x,원본 x)를 넣어서 우선순위를 맞추고 출력할 때는 [1]을 통해서 뒤의 원본을 출력한다