백준(BaekJoon) 1927, 11279, 11286번 : 최소 힙, 최대 힙, 절댓값 힙 - python 문제 풀이

❓1927번, 11279번, 11286번 : 최소 힙, 최대 힙, 절댓값 힙

📈 문제 요약

각각 최소 힙, 최대 힙, 절댓값 힙을 구현해서 입력받은 x가 자연수인 경우 힙에 삽입하고 0인 경우 힙에서 삭제 후 출력하는 연산을 구현하는 문제. 힙이 비어있을 때 출력 연산 시 0을 출력한다.

🤨 접근법

파이썬에서 heap 자료구조를 사용하기 위해 heapq 모듈을 활용할 수 있다. 기본적으로 heapq 모듈에서 지원하는 연산은 모두 최소 힙을 만족하도록 설계되어 있다.

보다 여러 메소드가 더 있지만, 유용하게 활용할 수 있는 메소드는 다음의 네 개의 메서드이다.

• heapq.heappush(heap, item)
  • 최소 힙의 성질을 만족시키도록 item을 heap에 넣는다.
• heapq.heappop(heap)
  • 최소 힙의 성질을 만족시키도록 최소 힙에서 최소 값을 반환 후 삭제한다.
  • 힙이 비어있을 때 메소드를 실행하면 IndexError가 발생한다.
• heapq.heappushpop(heap, item)
  • 최소 힙의 성질을 만족시키도록 item을 heap에 넣고 최소 값을 반환 후 삭제한다.
  • 각각의 연산을 따로 실행하는 것 보다 효율적이다.
• heapq.heapify(x)
  • 자료구조 x를 최소 힙을 만족하도록 변환한다. 선형 시간(O(N))을 만족한다.

문제에 대한 코드와 함께 사용 예시를 살펴보자.

🔡 코드1. 최소 힙(1927번)

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

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

for _ in range(N):
    x = int(input())
    if x == 0:
        if not heap:
            print(0)
        else:
            print(heappop(heap))
    else:
        heappush(heap, x)

단순히 입력받은 x가 0이 아닐 경우 힙에 push하고, 0일 때 힙에서 pop하는 연산으로 최소 힙을 만족한다.

그렇다면 최대 힙은 어떻게 구현할 수 있을까?

🔡 코드 2. 최대 힙(11279번)

• 방법 1

  import sys
  from heapq import heappush, heappop
  
  input = sys.stdin.readline
  
  N = int(input())
  heap = []
  
  for _ in range(N):
      x = int(input())
      if x == 0:
          if not heap:
              print(0)
          else:
              print(-1*heappop(heap))
      else:
          heappush(heap, -1*x)

  위와 같이 heap에 push할 때 음수로 변환해서 삽입을 해준다. 이러면 실제 가장 큰 수가 음수로 변환되면서 가장 작은 수가 되기 때문에 최소 힙을 만족하는 과정에서 가장 높은 우선순위를 가지게 된다. 그러므로 힙에 들어가 있는 수들은 모두 음수로 변환되어있기 때문에 이를 pop 해서 활용하기 위해서는 다시 부호를 반전시켜 활용해야 한다.
  
• 방법 2

  import sys
  from heapq import heappush, heappop
  
  input = sys.stdin.readline
  
  N = int(input())
  heap = []
  
  for _ in range(N):
      x = int(input())
      if x == 0:
          if not heap:
              print(0)
          else:
              print(heappop(heap)[1])
      else:
          heappush(heap, (-1*x, x))

  힙에 삽입 시 iterable한 collection을 사용해 인덱스 0에 부호를 반전시킨 값을, 인덱스 1에 원래 값을 넣어 주면, 인덱스 0 값을 기준으로 최소 힙을 만족시키게 된다. 그렇다면 인덱스 1에 있는 원래의 값들은 최대 힙으로 정렬되게 되어, pop후 인덱스 1에 있는 원소들을 활용하면 된다.
  

🔡 11286번 : 절댓값 힙

절댓값이 작은 값이 높은 우선순위를 가지도록 힙을 구성해야할 때는 어떻게 해야할까? 최대 힙을 만드는 두 번째 방법처럼 접근하면 간단하다.

import sys
from heapq import heappop, heappush

input = sys.stdin.readline

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

for _ in range(N):
    x = int(input())
    if x != 0:
        heappush(heap, (abs(x), x))
    else:
        if not heap:
            print(0)
        else:
            print(heappop(heap)[1])

최소 힙 내의 원소들이 iterable한 collection으로 되어있을 경우 최소값 즉, 우선순위를 판단하는 기준은 0번 째 인덱스이다. 따라서 삽입 시 튜플의 형태로 0번째 인덱스에는 x의 절댓값을, 1번째 인덱스에는 원래의 값 x를 넣어주면 절댓값이 작은 순으로 최소 힙이 구성되게 된다.

따라서 pop연산시 첫번째 인덱스를 활용하는 방법으로 구현할 수 있다.