백준 1655 가운데를 말해요

import heapq

n = int(input())
g = []
for _ in range(n):
    tmp = []
    t = int(input())
    g.append(t)
    heapq.heapify(g)
    while g:
        x = heapq.heappop(g)
        tmp.append(x)
    g = tmp
    print(g[int((len(tmp)-1)//2)])

시간초과 >>pop과 push로만 코드를 짜야함

import heapq
import sys

input = sys.stdin.readline
n = int(input())
small = []
big = []

for _ in range(n):
    t = int(input())
    if len(small) == len(big):
        heapq.heappush(small, -t)
    elif len(small) > len(big):
        heapq.heappush(big, t)
    if big and -small[0] > big[0]:
        s = -heapq.heappop(small)
        b = heapq.heappop(big)
        heapq.heappush(small, -b)
        heapq.heappush(big, s)
    print(-small[0])

두 개의 힙을 사용한다
작은 것들을 넣는 힙 (-> 최대힙으로 구성), 큰 것들을 넣는 힙 (-> 최소 힙으로 구성)
1 . 두 힙의 크기가 같으면 작은 쪽으로 들어간다
2 . 나머지 경우는 큰 쪽으로 들어간다 (어차피 len(small) > len(big) 이 경우만 생기고 len(small) < len(big) 이 경우는 생길 수 없음
3 . 만약 넣었는데 작은 것들 중 가장 큰거 > 큰 것들 중 가장 작은거 되면 둘이 바꿔준다
참고로 sys.stdin.readline 안쓰면 시간초과 남