[Algorithm] 백준 2696 중앙값 구하기 : C++, 힙, 재채점 수정

2696번: 중앙값 구하기

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

int t, m;
long long input;

int main(){
    // init
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // input
    cin >> t;

    while (t--){

        priority_queue<long long> maxQ;
        priority_queue<long long> minQ;

        cin >> m;
        cout << (m/2) + 1 << '\n';

        // solve
        for(int i = 0; i < m; i++){
            cin >> input;

            if(maxQ.size() > minQ.size())
                minQ.push(-input);
            else
                maxQ.push(input);

            if(!maxQ.empty() && !minQ.empty()){
                if(maxQ.top() > -minQ.top()){
                    long long minValue = -minQ.top();
                    long long maxValue = maxQ.top();

                    minQ.pop();
                    maxQ.pop();

                    minQ.push(-maxValue);
                    maxQ.push(minValue);
                }
            }

            if(i % 2 == 0)
                cout << maxQ.top() << " ";
        }

        cout << '\n';
    }
}

---

 이전에 풀었던 문제인데 재채점 후 틀렸습니다가 나와서 다시 풀어본 문제입니다. 일단 최소 힙, 최대힙 2개를 가지면서 이 2개를 이용해 '인풋 -> 최대힙이 0~1개 원소 더 많게 넣기 -> 이후 최소, 최대를 찾아서 교체하기' 를 해주면 되는 문제입니다.

 

 여기서 재채점 오류가 난건 주어지는 입력들이 32비트 부호없는 정수라 음수 -> 양수 부호 전환시 -2147483648이 부호가 바뀌면 절댓값이 나오지 않는 오류가 있어서 그랬습니다. 이를 위해 long long로 변환해서 풀이를 하니 잘 풀렸습니다.