백준 중앙값 구하기, 2696 (c++)

문제

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

문제 설명

중앙 값 구하기이다

• 이문제는 처음 시간초과를 겪은 뒤 방향을 바꾸었다 혼자 아이디가 떠오르지 않아서 다른분이 도음울 주셨다 우선 우큐문제이다.

• 현재 min, max우큐 두가지를 가지고 있다고 정한다

• 둘째 max우큐에 중앙값을 가지게 하되, min우큐에는 중앙값보다 큰값들을 가지고 있게한다

• 셋째 두가지 값들의 균형을 유지하도록한다

• 위의 경우를 토대로 비어있을 때는 mxq에 넣고 나머지 경우에는 두가지를 보면된다

  • 만약 mxq.size() == mnq.size()가 같을 경우(다음 들어오는 수가 중앙 값의 후보가 된다) 현재 들어오는 값이 max.top보다 작으면 mxq에 넣고 그렇지 않고 크다면 mnq에는 넣는다

  • 왜냐? mxq에는 중앙값이하의 값들을 유지, mnq에는 중앙값 이상의 값들을 유지하기 위해서이다.

  • (mxq.size() > mnq.size())의 경우에는 만약 현재 중앙값 후보보다 값이 더 크다면 그냥 바로 mnq에 넣으면된다 그런데 값이 더 작게된다면 mxq에 넣어야하는데 이미 mxq는 사이즈가 더 큰데 또 넣는다면 균형에 문제가 생기기때문에 top값을 mnq네 넣고 그 후에 mxq에 새로운 값을 넣는다

소스

#include <bits/stdc++.h>

using namespace std;

int t, n, s, e, mid;
int main() {

    cin >> t;

    while (t--)
    {
        cin >> n;
        vector<int> v, ans;
        int ansCnt = 0;
        v.resize(n + 1);
        for (int i = 1; i <= n; i++) cin >> v[i];


        priority_queue<int, vector<int>> mxq; //중앙값이하들을 삽입
        priority_queue<int, vector<int>, greater<int>> mnq; // 중앙값 이상들을 넣는다 

        for (int i = 1; i <= n; i++)
        {

            if ((int)mxq.size() == 0) mxq.push(v[i]);
            else if (mxq.size() == mnq.size()) {
                // 1 2가 있을 때 다음 들어오는 수가 중앙 값이다 
                    //들어온 수가 현재 중앙값(mxq.top())보다 크다면 중앙값을 교체해주어야합니다.
                if (v[i] > mxq.top()) {
                    mnq.push(v[i]);
                    mxq.push(mnq.top());
                    mnq.pop();
                }
                else {
                    mxq.push(v[i]);
                }
            }
            else if (mxq.size() > mnq.size()) {
                //  들어오는 값이 중앙 값보다 작으면 원래 mxq에 넣어야하는데  바로 넣으면 크기의 균형이 무너지게된다 그래서 현재 중앙값을 mnq에 넣고 현재 들어오는 값을 mxq에 넣는다  
                if (mxq.top() > v[i]) {
                    mnq.push(mxq.top());
                    mxq.pop();
                    mxq.push(v[i]);
                }
                else {
                    mnq.push(v[i]);
                }
            }

            if (i % 2) {
                ansCnt++;
                ans.push_back(mxq.top());
            }
        }
        cout << ansCnt << endl;
        for (auto a : ans) cout << a << " ";
        cout << endl;
    }

    return 0;
}