[Baekjoon/🥈SilverⅡ] 11279: 최대 힙

Intro

Algoritm👩‍💻: heap 직접 구현

#21.01.19
#11279: 최대 힙
import sys
N = int(input())
heap = [0]

def push(x):
  heap.append(x)
  idx = len(heap)-1
  while 1:
    if idx == 1 or x < heap[idx//2]:
      break
    else:
      heap[idx] = heap[idx//2]
      heap[idx//2] = x
      idx //= 2

def pop():
  print(heap[1])
  lst = heap[-1]
  heap[1] = lst
  del(heap[-1])
  idx = 1
  while 1:
    if len(heap) < idx*2 + 1:
      break
    elif len(heap) >= idx*2 + 2:
      if heap[idx*2] > heap[idx*2 + 1]:
        max = idx*2
      else:
        max = idx*2 + 1
      if lst < heap[max]:
        heap[idx] = heap[max]
        heap[max] = lst
        idx = max
      else:
        break
    elif lst < heap[idx*2 ]:
      heap[idx] = heap[idx*2]
      heap[idx*2] = lst
      idx = idx * 2
    else:
      break

for i in range(N):
  x = int(sys.stdin.readline())
  if x == 0:
    if len(heap) == 1:
      print(0)
    else:
      pop()
  else:
    push(x)

👩 힙을 직접 구현해보았다. 오답은 아니었으나 많은 시간을 필요로 했고, 코드를 약간 수정할 경우, 시간초과가 되었다ㅜㅜ

Algoritm👩‍💻: heapq

• heapq 모듈은 일반 리스트를 마치 최소 힙처럼 사용할 수 있도록 한다.

• 우리가 구현해야 할 것은 최대 힙이므로 들어가는 값에 -1을 곱함으로써 가장 큰 값이 가장 작은 값이 되도록 변경하면 된다.

#21.01.19
#11279: 최대 힙
import sys
import heapq

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

for _ in range(N):
  x = int(sys.stdin.readline())
  if x == 0:
    try:
      print(-1 * heapq.heappop(heap))
    except:
      print(0)

  else:
    heapq.heappush(heap, -x)

• heapq는 최소 힙을 지원하므로 들어가는 값에 -1을 곱해 음수형태로 값을 삽입한다.
  • 최대 값을 최소 값으로 변경한다.
• 출력할 때는 pop한 값에 -1을 곱해 원래 값을 출력한다.

참고📃

• https://www.daleseo.com/python-heapq/
• https://claude-u.tistory.com/152

이번 포스팅은 여기서!

끝!! ~(˘▾˘~)