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

문제

1655번: 가운데를 말해요

풀이

• 최대 힙, 최소 힙을 이용해서 풀이
• 최대 힙의 루트 값이 중간 값이 되기 위한 조건
  • 최대 힙의 크기는 최소 힙과 같거나(짝수개) 1 커야 함(홀수개)
  • 최대 힙의 루트 값은 최소 힙의 루트 값보다 작아야 함
• 알고리즘
  • 최대 힙과 최소 힙에 번갈아서 값을 넣음
  • 최대 힙의 루트 값이 중간 값이므로 최대 힙에 먼저 삽입해야 함
  • 최대 힙의 루트 값이 최소 힙의 루트 값 보다 크다면 둘의 자리를 바꿔서 최대 힙의 루트 값이 중간값을 유지하도록 함

코드

import sys
import heapq

n = int(sys.stdin.readline())
input = [int(sys.stdin.readline()) for _ in range(n)]
heap = []

for i in input:
	if i == 0:
		print(heapq.heappop(heap)[1] if heap else 0)
	else:
		heapq.heappush(heap, (-i, i))