[백준] 2696번 중앙값 구하기 _ 문제 풀이

1. 문제

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

2. 풀이

배열을 모두 입력 받은 후에, 요구하는 크기만큼 정렬하여 중간값을 출력해주면 쉽게 문제풀이 할 수 있습니다. 하지만 매번 정렬하는데 시간이 매우 걸립니다. 시간을 줄이기 위해서는 최소힙, 최대힙을 이용하여 중간값보다 작은 숫자, 큰 숫자를 따로 저장하고 있다가 매번 힙의 크기를 맞춰주면서 수를 추가해주면 훨씬 더 빠르게 풀이 할 수 있습니다.

T = int(input())
for _ in range(T):
    M = int(input())
    print(M//2 + 1)
    arr = []
    for __ in range((M-1)//10+1):
        arr.extend(list(map(int, input().split())))
    for i in range(1, len(arr)+1, 2):
        print("%d" % sorted(arr[:i])[i//2], end=' ')
        if (i + 1) % 20 == 0:
            print()
    print()

PREVIOUS[백준] 2304번 창고 다각형 _ 문제 풀이

NEXT[백준] 2002번 추월 _ 문제 풀이