[BOJ] 중앙값 구하기 2696번 C++

 

 

문제

어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오.

예를 들어, 수열이 1, 5, 4, 3, 2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주어진다. 원소는 한 줄에 10개씩 나누어져있고, 32비트 부호있는 정수이다.

출력

각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 10개씩 출력해야 한다.

 

구현

 

알고리즘 분류가 우선순위 큐라고 되어있는데 우선순위 큐로는 최소값, 최대값만 구할 주 있지 중간 n번째 작은 값과 같은 값은 구할 수 없다

그래서 어떻게 푸는지 여러 블로그를 확인해보니 최소힙과 최대힙을 활용하면 중간값을 구할 수 있음을 알게 되었다!

 

예시와 같이 1, 5, 4, 3, 2인 수열을 가지고 있다고 했을 때

1. 먼저 최대힙이 비어있다면 최대힙에 값을 넣는다

2. 최대힙의 top값과 값을 비교해 같거나 작으면 최대힙에, 크면 최소힙에 넣는다

3. 이때 만약 최대힙과 최소힙의 차이가 1이상이라면 최대힙의 top을 최소힙에 넣는다

4. 만약 최소힙의 사이즈가 최대힙의 사이즈보다 커도 최소힙의 top을 최대힙에 넣는다

 

i	최대힙	최소힙
1	1
2	1	5
3 (이 때, 최대힙보다 최소힙 사이즈가 크므로 최소힙의 top을 최대힙에 넣음)	4,1	5
4 (이때, 최대힙과 최소힙의 차이가 2이상이므로 최대힙의 top을 최소힙에 넣음)	3,1	5,4
5	3,2,1	5,4

 

생각해보면 은근히 간단한 풀이다

최대힙과 최소힙을 사용해서 중간값을 구할 수 있음을 알게 되었다~!

 

 

 

코드

#include<bits/stdc++.h>
using namespace std;

int main() {
    int T; cin>>T;
    while(T--) {
        int m; cin>>m;
        priority_queue<int, vector<int>> mx_pq;
        priority_queue<int, vector<int>, greater<>> mn_pq;

        vector<int> ans;

        for(int i=1; i<=m; i++) {
            int x; cin>>x;

            if(mx_pq.empty() || x <= mx_pq.top()) mx_pq.push(x);
            else mn_pq.push(x);

            if(mx_pq.size() > mn_pq.size() + 1) {
                mn_pq.push(mx_pq.top());
                mx_pq.pop();
            }
            else if(mn_pq.size() > mx_pq.size()) {
                mx_pq.push(mn_pq.top());
                mn_pq.pop();
            }

            if(i % 2 == 1) ans.push_back(mx_pq.top());
            
        }
        cout<<ans.size()<<"\n";
        for(int i=0; i<ans.size(); i++) {
            if(i != 0 && i%10 == 0) cout<<'\n';
            cout<<ans[i]<<" ";

        }
        cout<<'\n';

    }
}