백준2696 - 중앙값 구하기

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

2696번: 중앙값 구하기

트리를 이용한 자료구조이다. 중복된 원소를 입력 받기 위해서 multiset을 이용하였다. 중앙값을 구하면 되는데 중앙값은 평균이 아니고 주어진 수열에서 오름차순이나 내림차순으로 배열하였을 때 가장 중앙에 위치한 원소를 가리켜 말한다. 따라서 set이나 multiset은 입력과 동시에 오름차순으로 정렬해주기 때문에 이 문제에 적합하다고 생각하였다.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int T;
    
    cin >> T;
    while(T--) {
        int M, num;
        int show = 1;
        vector<int> v;
        multiset<int> st;
        
        cin >> M;
        for(int i = 0; i < M; i++) {
            cin >> num;
            v.push_back(num);
        }
        
        cout << M / 2 + 1<< '\n';
        
        for(int i = 0; i < M; i++) {
            st.insert(v[i]);
            if((i + 1) % 2 == 1) {
                auto it = st.begin();
                for(int j = 0; j < (i + 1) / 2; j++) {
                    it++;
                }
                cout << *it << ' ';
                if(show % 10 == 0 && show != 0) {
                    cout << '\n';
                }
                show++;
            }
        }
        cout << '\n';
    }
}