[파이썬] [힙] 백준 2696 중앙값 구하기

문제

https://www.acmicpc.net/problem/2696

2696번: 중앙값 구하기

 

코드

import sys
import heapq
input=sys.stdin.readline

def sol(li):
    small=[]
    big=[]
    middle=li[0]
    result=[middle]

    for idx,val in enumerate(li[1:],1):
        if val > middle:
            heapq.heappush(big,val)
        else:
            heapq.heappush(small,-val)
        if idx%2==0:
            if len(small) > len(big):
                heapq.heappush(big,middle)
                middle=-heapq.heappop(small)
            elif len(small) < len(big):
                heapq.heappush(small,-middle)
                middle=heapq.heappop(big)
            result.append(middle)
    print(len(result))
    idx=0

    for _ in range(len(result)//10):
        print(*result[idx:idx+10])
        idx+=10
    print(*result[idx:])


t=int(input())
for _ in range(t):
    m=int(input())
    mok=m//10
    na=m%10

    li=[]
    if mok==0:
        li.extend(map(int,input().split()))
    else:
        for i in range(mok+1):
            li.extend(map(int, input().split()))
    sol(li)