백준 2696 <중앙값 구하기> Python

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

---

입력 가운데 여러번 중앙값을 구하는 문제는 일반적으로 최대힙과 최소힙을 연결해 푸는 경우가 대부분입니다. 하지만 단순히 정렬이 여러 번 이루어지기 때문에 정렬의 속도가 문제라면 이분탐색을 이용한 정렬을 통해 해결할 수 있습니다. 이런 방식은 매번 모든 데이터를 정렬하지 않기 때문에 보다 빠르게 문제를 해결할 수 있습니다.

 

bisect.insort 함수를 사용해 새로운 데이터가 추가될 때 마다 해당 데이터가 들어갈 수 있는 위치를 이분탐색으로 찾아 삽입했습니다.

---

import sys

from bisect import insort

input = sys.stdin.readline

def solution(M, data_list):

    # 결과 리스트

    result = []

    # 하나씩 데이터를 넣을 리스트

    input_list = []

    # 하나씩 데이터를 넣기

    for i in range(M):

        insort(input_list, data_list[i])

        # 홀수면

        if not i%2:

            # 중앙값 넣기

            result.append(input_list[i//2])

    return result

# 입력

T = int(input().strip())

for _ in range(T):

    M = int(input().strip())

    data_list = []

    for __ in range(M//10 + 1):

        data_list += list(map(int, input().strip().split()))

   

    result = solution(M, data_list)

    print(len(result))

    for i in range(0, len(result), 10):

        print(*result[i:i+10])