[PS] 백준 #2696 중앙값 구하기 문제 풀이

[ 문제 풀이 ]

• Problem : 백준 #2696
• 구분 : ds, pq(우선순위 큐)
• 난이도 : Gold 3
• 풀이 방법 :
  • "각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다" 라는 문제 조건에 따라 홀수번째때마다 중앙값을 찾아야 합니다.
  • 가장 단순한 방법은 홀수번째 수가 들어올때 마다 배열(vector)을 정렬해서 length/2 인덱스를 출력해주는 것인데 아마 메모리 초과/시간초과가 납니다.
  • 따라서, 큐를 2개써서 해결해주어야 합니다. min-heap, max-heap인 pq를 각각 선언해서, max-heap top에 중앙값을 위치시켜주고 홀수번째 수가 들어올때마다 출력해주면 됩니다.
    
    
  • 로직은 다음과 같습니다.
    • 기본적으로 mxq에는 중앙값 + 중앙값 미만의 값, mnq에는 중앙값 이상의 값을 넣어 유지시켜줍니다.
    • 만약 mxq와 mnq가 모두 비었다면, mxq에 수를 넣어줍니다. (초기상태)
    • mxq.size() > mnq.size() 인 경우,
      • 들어온 수가 현재 중앙값(mxq.top())보다 작다면 중앙값을 교체해주어야 합니다. mxq.top을 mnq에 넣어주고 현재 값을 mxq에 넣어줍니다.
      • 들어온 수가 현재 중앙값(mxq.top())보다 크거나 같다면 mnq에 넣어줍니다.
    • mxq.size() == mnq.size()인 경우,
      • 들어온 수가 현재 중앙값(mxq.top())보다 크다면 중앙값을 교체해주어야합니다. 먼저 mnq에 넣은 후 mnq.top(중앙값보다 큰 값들 중 최솟값)을 mxq에 다시 넣어줌으로서 중앙값 업데이트를 할 수 있습니다.
      • 그 이외의 경우는 그냥 mxq에 넣어줍니다.
  • 시간복잡도는 log(mlogm)입니다.

[ 🤟🏻 Code from ss-won ]

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
using namespace std;
int t, m, input, c = 0;
priority_queue<int, vector<int>, less<int>> mxq;
priority_queue<int, vector<int>, greater<int>> mnq;

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cin >> t;
    while(t--){
        cin >> m;
        priority_queue<int, vector<int>, less<int>> mxq;
        priority_queue<int, vector<int>, greater<int>> mnq;
        c = 0;
        cout << (m/2)+1 << "\n";
        for(int i=1;i<=m;i++){
            cin >> input;
            if(mxq.empty() && mnq.empty()){
                mxq.push(input);
            }
            else if(mxq.size() > mnq.size()){
                if(mxq.top() > input){
                    mxq.push(input);
                    mnq.push(mxq.top()); mxq.pop();
                }
                else{
                    mnq.push(input);
                }
            }
            else if(mxq.size() == mnq.size()){
                if(mxq.top() < input){
                    mnq.push(input);
                    mxq.push(mnq.top()); mnq.pop();
                }
                else{
                    mxq.push(input);
                }
            }
            if(i%2==1){
                cout << mxq.top() << " ";
                c++;
                if(c % 10 == 0) cout << "\n";
            }
        }
        cout << "\n";
    }
    return 0;
}