Baekjoon-2696)중앙값 구하기

백준 사이트 URL : https://www.acmicpc.net/problem/2696

문제 분석

입력 : 테스트크기 T, 수열의 크기 M, 그리고 M길이의 수열의 값

출력 : 수열에서 중앙값의 개수를 구한다(단, 중앙값은 홀수개를 기준으로 생성된다), 생성되는 중앙값들을 출력한다.

제한 : 시간제한 1초, 메모리제한 128MB

아이디어 : 단순히 배열을 통행 입력받고 매 홀수 번째 마다 정렬 후 가운데 인덱스를 출력하는 방법도 있다.
              하지만, 그 경우 시간초과의 위험이 있다. 
            : 2개의 Heap인 Max_Heap과 Min_Heap을 통해 중앙값과 데이터의 입력을 효육적으로 만들 수 있다.

       

          즉, 새로운 값을 넣고 난 후의 두 Heap의 사이즈가 다를 시 Max_Heap의 top()값이 중앙값이 된다.

소스코드

      

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<queue>
#include<functional>
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n,num;
        cin >> n;
        cout << (n + 1) / 2 << endl;
        priority_queue<int,vector<int>, greater<int>> min_heap;
        priority_queue<int> max_heap;
        for (int i = 1; i <= n; i++) {
            cin >> num;
            if (max_heap.size() == min_heap.size()) {
                if (min_heap.empty()) {
                    max_heap.push(num);
                }
                else {
                    if (min_heap.top() <= num) {
                        int t = min_heap.top();
                        min_heap.pop();
                        min_heap.push(num);
                        num = t;
                    }
                    max_heap.push(num);
                }
            }
            else {
                if (max_heap.top() > num) {
                    int t = max_heap.top();
                    max_heap.pop();
                    max_heap.push(num);
                    num = t;
                }
                min_heap.push(num);
            }
 
            if (i & 1) {
                cout << max_heap.top() <<" ";
            }
        }
    }
 
    return 0;
}