[백준] 1655: 가운데를 말해요

1 <= n <= 100000
시간 제한: PyPy3: 0.6 초

문제 풀이 전략
1. 최대힙 (left), 최소힙(right) 생성
2. left[0] 이 right[0] 보다 크면
3. -left[0] / right[0] heappop
4. right에 -left[0]을 minheap으로 넣기 (변수로 따로 저장)
5. left에 right[0] 을 maxheap으로 넣기

import heapq
import sys
import time
input = sys.stdin.readline
n = int(input())

left = [] # max heap
right = [] # min heap

for i in range(n):
	tmp = int(input())
	if len(left) == len(right):
		heapq.heappush(left, -tmp)
	else:
		heapq.heappush(right, tmp)
	if right and -left[0] > right[0]:
		lf = -heapq.heappop(left)
		rg = heapq.heappop(right)
		heapq.heappush(left, -rg)
		heapq.heappush(right, lf)
	print(-left[0])