[알고리즘] 1655 가운데를 말해요

1655 가운데를 말해요

n개의 숫자가 입력됨에 따라 숫자가 입력될 때마다 현재까지 입력된 숫자들의 중간값을 출력해야 하는 문제이다. n은 1보다 크므로 숫자 하나를 먼저 입력받아두었다.

우선순위 큐를 두개 사용하여 pq_left큐는 중간값보다 큰 수들과 중간값을 저장하고 pq_right에는 중간값보다 작은 수들을 저장한다. pq_left는 오름차순, pq_right는 내림차순으로 정렬되게 만들어서, pq_left.top()이 중간값이 되도록 하고, pq_right.top()은 중간값에 가장 가까운 값이 되도록 한다. i를 2부터 n까지 증가하면서 입력을 받는데, 이 때 i는 현재 입력받는 수를 포함한 현재까지의 숫자 개수이다.

i가 홀수라면 두 큐의 최종 상태는 pq_left.size()+1 = pq_right.size()이고, 짝수라면 pq_left.size()+2 = pq_right.size() 이다. 이에 따라 i가 짝수인지 홀수인지 구분하여 코드를 작성해주면 되었다.

풀이

#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n;
priority_queue<int,vector<int>,greater<int>> pq_left;
priority_queue<int> pq_right;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;

    int tmp; cin>>tmp;
    pq_left.push(tmp);
    cout<<pq_left.top()<<"\n";

    for(int i=2;i<=n;i++){
        cin>>tmp;
        if(i % 2 == 0){
            if(tmp >= pq_left.top()){
                pq_left.push(tmp);
            }else{
                pq_right.push(tmp);
                pq_left.push(pq_right.top());
                pq_right.pop();
            }
        }else{
            if(tmp > pq_left.top()){
                pq_right.push(pq_left.top());
                pq_left.pop();
                pq_left.push(tmp);
            }else{
                pq_right.push(tmp);
            }
        }
        cout<<pq_left.top()<<"\n";
    }
}