백준(S1) 11286번: 절댓값 힙(파이썬 Python3)

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

11286번: 절댓값 힙

파이썬으로 heap문제를 풀려면 heapq라는 모듈을 알아야 한다.

https://solution-is-here.tistory.com/114

백준(S2) 11279번: 최대 힙(파이썬, Python3)및 heapq 설명

위 링크를 보고 오면 heapq에 대해 쉽게 이해하실 수 있습니다.

heapq를 이해해야 문제를 풀수 있기 때문에 꼭 보시길 추천합니다.

 

문제를 보면 다른 힙 문제들과 다른 점을 찾을 수 있습니다.

바로 힙을 제거할때 절댓값이 가장 작은 값을 출력하고 절댓값이 가장 작은 값이 여러 개 일 때는 가장 작은 수를 출력하는 것입니다. 이를 해결하기 위해서는 heappush함수를 잘 사용해야 합니다.

heapq.heappush(heap,(abs(x),x))

원래는 heappush를 하고 리스트 이름과 변수 하나만 입력 했는데 이렇게 두 개를 넣으면 앞에 있는 절댓값을 기준으로 최소 힙에 숫자를 넣고 두 번째 숫자를 이용해서 절댓값이 똑같을 때 더 작은 숫자를 출력할 수 있게 해줍니다.

이것만 알면 이 문제는 정말 쉽게 풀 수 있다고 생각합니다.

 

출력할 때 절댓값이 아닌 절댓값 처리 하기 전 수가 궁금하면 첫 번째 인덱스를 출력하면 됩니다.

min = heapq.heappop(heap) 
print(min[1])

 

정답코드:

import sys
import heapq
heap = []
input = sys.stdin.readline
 
num = int(input())
for i in range(num):
    x = int(input())
    if x != 0:
        heapq.heappush(heap,(abs(x),x))
    else:
        if len(heap) > 0: 
            min = heapq.heappop(heap) 
            print(min[1])
        else:
            print("0")