[백준-2696] 중앙값 구하기

heap 2개를 가지고 Nlog(N) 의 시간 내로 중앙값을 뽑아내는 로직을 사용하면 쉽게 풀린다. heap 2개는 다음과 같다.

• 절반의 작은 값들을 저장하는 max heap
• 절반의 큰 값들을 저장하는 min heap

이 때 min heap 이 max heap 크기 이상의 특징을 계속 가지도록 한다면 홀 수 개의 값이 입력되었을 때 min heap 의 top 을 출력하도록 하면 쉽게 풀린다.

예를 들어 입력되는 수가 1, 5, 4, 3, 2 라고 해보자.

1. 1 이 들어오게 되면 먼저 min heap 에 넣는다.
2. 그 후 5가 들어오면 size 가 작은 max heap 에 넣는다.
3. 넣은 후 max heap 의 top과 min heap의 top 을 비교해서 max heap 의 것이 더 크다면 서로 top 을 swap 해준다.
4. 2~3 을 반복한다.

이렇게 되면 위에서 말했듯이 절반의 작은 값들은 max heap 에 저장되고, 절반의 큰 값들은 min heap 에 저장되어 중간값을 바로바로 꺼내어 확인할 수 있게 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

int n, m;
int arr[10001];
priority_queue<int, vector<int>, greater<int>> minQ;
priority_queue<int, vector<int>, less<int>> maxQ;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int tc;
    cin >> tc;
    vector<int> ans;
    for (int i = 0; i < tc; i++) {
        cin >> n;
        ans.clear();
        memset(arr, 0, sizeof(arr));
        for (int j = 1; j <= n; j++) {
            cin >> arr[j];

            if (minQ.empty()) 
                minQ.push(arr[j]);
            else if (minQ.size() > maxQ.size()) 
                maxQ.push(arr[j]);
            else if (maxQ.size() <= maxQ.size()) 
                minQ.push(arr[j]);
            // 똑같음
            if (!maxQ.empty() && maxQ.top() > minQ.top()) {
                int temp = maxQ.top();
                maxQ.pop();
                maxQ.push(minQ.top());
                minQ.pop();
                minQ.push(temp);
            }

            if (j % 2 != 0) {
                ans.push_back(minQ.top());
            }
        }
        cout << ans.size() << endl;
        for (int i = 0, cnt = 0; i < ans.size(); i++) {
            cout << ans[i] << " ";
            cnt += 1;
            if (cnt % 10 == 0) cout << endl;
        }
        cout << endl;

        while (!maxQ.empty()) maxQ.pop();
        while (!minQ.empty()) minQ.pop();
    }

    return 0;
}

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

2696번: 중앙값 구하기