[백준 1655번] 가운데를 말해요 (Python3)

import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N = int(input())

maxhq = []
minhq = []
heappush(maxhq,10**6)
heappush(minhq,10**6)

for i in range(N):
  n = int(input())
  if n>minhq[0]:
    heappush(minhq,n)
  else:
    heappush(maxhq,-n)
  while True:
    if len(minhq)>len(maxhq):
      heappush(maxhq,-heappop(minhq))
      continue
    if len(maxhq)>len(minhq)+1:
      heappush(minhq,-heappop(maxhq))
      continue
    break
  print(-maxhq[0])

최대힙, 최소힙을 이용하는 문제이다.

 

아마 대부분 문제를 보자마자 최대힙 최소힙으로 중간값을 구현해야할 것이라는건 쉽게 떠올릴 수 있을 것이다.

문제는 이제 어떻게 구현을 하느냐인데, 내가 사용한 방법은

 

1. 최소힙, 최대힙 둘 다 10^6을 넣는다. (인덱스 에러 방지)

2. 최소힙에는 반 잘랐을때 더 큰값들, 최대힙에는 반 잘랐을때 더 작은값들이 들어가게 된다.

3. 입력받은 n값이 최소힙의 가장 작은값 (minhq[0])보다 클 경우, 최소힙에 삽입

4. 아닐 경우 최대힙에 음수로 삽입

5. 최대힙의 길이가 최소힙보다 더 클 경우, 최대힙의 가장 큰 값을 최소힙에 삽입, 반대는 반대로

6. -maxhq[0] 값 출력

 

이때 나는 5번에서 while문을 썼는데 지금 코드를 보니까 굳이 while을 쓸 필요가 없을 것 같다.

 

 

오늘의 교훈) 우선순위 큐는 유용하다.