[백준] 절댓값 힙 풀이

sys.input.readline() 함수의 위력을 실감한 문제다.
heapq 모듈을 이용하여 문제 조건 그대로 구현해주면 된다.
예외사항으론 절댓값이 들어가므로 abs(a), a를 리스트나 튜플로 감싸서 push 해주면 된다.

절댓값이 같은 경우엔 자동으로 두 번째 요소로 정렬해주는 것으로 알고 있다. (틀린 경우 지적 부탁드립니다.)

그러므로 절댓값이 같은 요소가 있는 경우도 원래 값이 음수인 경우가 heappop 으로 출력되게 되는 것이다.

코드 상으론 어렵진 않으나, sys.stdin.readline() 함수를 사용하지 않으면 시간초과가 나게 된다.

나는 sys.stdin.readline()으로 받은 값을 int형으로 변경하여 문제를 풀었으나, 조금이라도 시간을 단축하기 위한 사람들은 int형으로 변경하지 않고 입력받은 문자열을 토대로 문제를 풀 수 있다.

그런 경우 sys.stdin.readline().rstrip() 즉 rstrip()까지 적용해 줘야 정답 처리가 된다. (개행 문자 제거 용이라고 알고 있다.)

import heapq,sys

N = int(input())
heap = []

for i in range(N):
    
    a = int(sys.stdin.readline())
    if a == 0:
        if not heap:
            print(0)
        
        else:
            print(heapq.heappop(heap)[1])
            
    else:
        heapq.heappush(heap, [abs(a), a])