[백준/Python] 11286 절댓값 힙 (우선순위 힙)

https://s2ej1n.tistory.com/136

앞서 포스팅했던 우선순위 힙을 사용하면 된다.

 

절댓값과 원래의 값을 함께 튜플로 넣어야함!

# x가 0아니면 배열에 x 추가 / 0이면 절댓값 작은거 출력
import heapq

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

for i in range(N):
    x = int(input())
    if x != 0 :
        heapq.heappush(heap, (abs(x),x))
        # 튜플 - 왼쪽꺼 비교하고, 그 다음 두번째 값 비교한다.
        # 절댓값 작은거 먼저 정렬하고, 그 다음 실제값 작은거 정렬.
    else :
        if len(heap) == 0:
            print(0)
        else:
            print(heapq.heappop(heap)[1])

시간초과

 

⇒ 파이썬 기본 입력이 느려서 생김. 그래서 sys.stdin.readline() 를 사용해야함.

(버퍼 기반으로 작동하여 훨신 빠름.)

 

# x가 0아니면 배열에 x 추가 / 0이면 절댓값 작은거 출력
import heapq
import sys

N = int(sys.stdin.readline())
heap = []

for i in range(N):
    x = int(sys.stdin.readline())
    if x != 0 :
        heapq.heappush(heap, (abs(x),x))
        # 튜플 - 왼쪽꺼 비교하고, 그 다음 두번째 값 비교한다.
        # 절댓값 작은거 먼저 정렬하고, 그 다음 실제값 작은거 정렬.
    else :
        if len(heap) == 0:
            print(0)
        else:
            print(heapq.heappop(heap)[1])