[백준] 2696번 : 중앙값 구하기

2696번: 중앙값 구하기

해당 문제는 우선순위 큐 문제로 중간값 말하기 문제와 똑같은 유형이다.

입력, 출력 포인트만 잘 잡아주면 끝이다.

import sys
import heapq
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    N = int(input())
    H = (N-1) // 10
    leftq = []
    rightq = []
    result = []
    temp = []
    for _ in range(H+1):
        temp += list(map(int, input().split()))

    cnt = 1  # 홀수 짝수 체크 cnt
    for num in temp:
        if len(leftq) == len(rightq):
            heapq.heappush(leftq, -num)
        else:
            heapq.heappush(rightq, num)

        if rightq and -leftq[0] > rightq[0]:
            num1 = heapq.heappop(leftq)
            num2 = heapq.heappop(rightq)
            heapq.heappush(leftq, -num2)
            heapq.heappush(rightq, -num1)

        if cnt % 2 == 1: # 홀수일때
            result.append(-leftq[0])
        cnt +=1

    print(len(result))
    cnt = 1
    for num in result:
        print(num, end=' ')
        if cnt % 10 == 0:
            print()
        cnt += 1

    if cnt % 10 != 0:
        print()