[Python] BOJ/백준 11286번 절댓값 힙

[문제]

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

11286번: 절댓값 힙

 

[풀이]

이전에 풀었던 7662번 이중 우선순위 큐와 유사하다.

2022.06.24 - [문제풀이/BOJ] - [Python] BOJ/백준 7662번 이중 우선순위 큐

[Python] BOJ/백준 7662번 이중 우선순위 큐

'힙(heap)'이란?

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 일종의 반정렬 상태(느슨한 정렬 상태) 유지
  • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
  • 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
• 힙 트리에서는 중복된 값 허용 (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

---

 

파이썬의 heapq 라이브러리가 제공하는 최소 힙을 이용한다. 

 

단, 절댓값을 기준으로 정렬해야하지만 출력되는 값은 기존 값이여야 한다.

튜플을 비교할 때 첫 번째 원소를 기준으로 정렬하기 때문에 (절댓값, 기존 값) 튜플 형식으로 힙에 넣는다.

 

 

[코드]

import sys
import heapq

heap = []
for _ in range(int(sys.stdin.readline())):
    x = int(sys.stdin.readline())

    if x == 0:
        if not heap:
            print(0)
        else:
            print(heapq.heappop(heap)[1])
    else:
        heapq.heappush(heap, (abs(x), x))