1655번 가운데를 말해요

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

1655번: 가운데를 말해요

 

백준 2696번과 같은 문제이다. 다만 짝수일때 중앙값은 두개의 값중 작은것으로 출력해야한다. ex) 1 2 3 4일때 2 3중 작은게 중앙값

#include <bits/stdc++.h>
#define l long long
#define INF 2e9
#define p pair<int,int>
using namespace std;

priority_queue<int,vector<int>,greater<>> MinQ;
priority_queue<int,vector<int>,less<>> MaxQ;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int n,num,temp;
    cin >> n;

    for(int i=1;i<=n;i++){
        cin >> num;
        if(i % 2 == 0) temp = MaxQ.top();

        if(MinQ.empty() && MaxQ.empty()) MaxQ.push(num);
        else if(MaxQ.size() > MinQ.size()){
            if(MaxQ.top() > num){
                MaxQ.push(num);
                MinQ.push(MaxQ.top());MaxQ.pop();
            }
            else MinQ.push(num);
        }
        else if(MaxQ.size() == MinQ.size()){
            if(MaxQ.top() < num){
                MinQ.push(num);
                MaxQ.push(MinQ.top());MinQ.pop();
            }
            else MaxQ.push(num);
        }

        if(i % 2 == 0) cout << min(temp,MaxQ.top()) << "\n";
        else cout << MaxQ.top() << "\n";
    }
}