[백준 11286번] 절댓값 힙 (Python/파이썬)

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

11286번: 절댓값 힙

이 문제는 파이썬의 우선순위 큐 자료구조가 무엇인지 안다면 어렵지 않게 해결할 수 있다.

파이썬에서는 우선순위 큐 자료구를 heapq모듈을 이용하여 사용할 수 있다.

 

스택: 가장 나중에 삽입된 데이터가 가장 먼저 나옴
큐: 가장 먼저 삽입된 데이터가 가장 먼저 나옴
우선순위 큐: 우선순위가 가장 높은 데이터가 가장 먼저 나옴

 

힙: 완전 이진트리의 일종으로 항상 루트 노드를 제거한다.파이썬 heapq에서는 최소 힙을 기본으로 한다.

최소힙 구조와 최대힙 구조

 

 

우선순위 큐 사용법은 다음과 같다.

import heapq
heap = []
heapq.heappush(heap, 1) ## heap에 1 추가
heapq.heappush(heap, 2) ## heap에 2 추가
heapq.heappop(heap) ## heap의 우선순위대로 삭제후 반환(파이썬은 최소 힙이 기본)

 

 

힙의 우선순위는 튜플로 heappush를 할때 튜플의 [0]번째 인덱스가 우선순위가 된다.

따라서 문제를 풀때는 튜플로 heappush를 하여 우선순위를 abs()를 이용하여 절댓값으로 하였다.

최대힙을 구현할때는 넣는 숫자가 x라면 (-x, x)로 heappush하여 최대힙을 구현할 수 있다.

코드는 다음과 같다.

 

import sys
from heapq import heappush, heappop

def Sol():
  input = sys.stdin.readline
  abs_heap = []
  N = int(input())
  for _ in range(N):
    x = int(input())
    if x != 0:
      heappush(abs_heap, (abs(x), x))  ## 튜플의 첫번째 인덱스로 우선순위 결정
    else:
      if abs_heap == []:
        print(0)
      else:
        print(heappop(abs_heap)[1])  ## 튜플이 pop되므로 튜플의 두번째 값을 출력
  
if __name__ == "__main__":
  Sol()

 

 

 

글에 대한 질문과 조언 모두 받습니다!