[백준 2696] 중앙값 구하기 (C++)

2696번: 중앙값 구하기

 

 

일단 처음에 들어오는 값은 반드시 최초의 중앙값이고 최초의 기준값이 된다.

그리고 앞으로 들어오는 값을 현재 기준과 비교해서 기준보다 크다면 최소 힙에, 기준보다 작다면 최대 힙에 넣어준다.

 

만약 지금까지 입력받은 수가 짝수라면 넘어간다. 하지만 홀수라면 현재 기준값이 중앙값이 되기 위해서는 최소 힙과 최대 힙에 들어있는 원소의 수가 서로 같아야 한다.

 

코드 : 만약 최소 힙의 수가 더 많다면 최소 힙에서 최상단 원소를 중앙값으로 둘 수 있을 것이고, 중앙값을 최대 힙으로 넣어 주면 최소, 최대 힙의 원소 수가 같게 되면서 중앙값을 최신으로 유지할 수 있게 된다.

 

한 번만 바꿔주면 되는 이유는 최소 힙과 최대 힙의 원소 개수의 차는 최대 2이므로 하나씩만 옮겨주면 계속해서 두 힙의 크기를 같게 맞춰줄 수 있기 때문이다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
using namespace std;
 
 
void solve(){
    int M = 0, middle, a;
    priority_queue<int, vector<int>, greater<int> > minheap;
    priority_queue<int> maxheap;
    vector<int> ans;
    
    cin >> M;
    cin >> middle;
    ans.push_back(middle);
    
    for(int i = 2; i <= M; i++){
        cin >> a;
        if(a > middle)  minheap.push(a);
        else            maxheap.push(a);
        
        if(i % 2 == 0) continue;
        else if(minheap.size() < maxheap.size()){
            minheap.push(middle);
            middle = maxheap.top();
            maxheap.pop();
            ans.push_back(middle);
        }
        else if(maxheap.size() < minheap.size()){
            maxheap.push(middle);
            middle = minheap.top();
            minheap.pop();
            ans.push_back(middle);
        }
        else ans.push_back(middle);
    }
    
    cout << M/2 + 1 << "\n";
    for(int i = 0; i < ans.size(); i++){
        if(i % 10 == 0 && i != 0){
            cout << "\n";
        }
        cout << ans[i] << " ";
    }
}
 
 
int main(){
    fastio
    int T;
    cin >> T;
    while(T--){
        solve();
        cout << "\n";
    }
    return 0;
}