[백준 파이썬] # 11286 절댓값 힙

Silver I

# 11286 절댓값 힙

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

11286번: 절댓값 힙

 

풀이

import heapq
import sys

heap = []
N = int(sys.stdin.readline())
for i in range(N):
    x = int(sys.stdin.readline())
    if x == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(heapq.heappop(heap)[1])
    else:
        heapq.heappush(heap, (abs(x), x))  # 문제 포인트

    # heap에 저장되는 과정을 확인하고 싶다면 시도해보기
    # print(heap)

 

후기

• # 1927번 최소 힙 문제 풀이에서 난이도가 한 계단 정도 위에 있는 문제다.
  
  
• heappush를 할 때, x의 절댓값과 x를 튜플에 담아준다.
  print(heap)을 통해 확인해 본 결과, 튜플의 0번째 인덱스를 기준으로 정렬되는 것을 볼 수 있었다.
  0번째 인덱스가 동일할 때 1번째 인덱스를 기준으로 정렬되었다.
  
  cf. N = 3, x = [1, -1, -1]을 시도했을 때 [(1, -1), (1, 1), (1, -1)] 처럼 출력된다.
  정렬이 안된 듯 싶었지만, 이진 트리를 그려 확인 해보면서 이해할 수 있었다.
  
  루트 노드 : (1, -1)
  하위 노드 : (1, 1), (1, -1)
  (1, 1)과 (1, -1)은 단순히 병렬적으로 위치한 것이므로 잘못된 것이 아니다.