백준 문제 1655번 가운데를 말해요 문제풀이 c++

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

1655번: 가운데를 말해요

 

문제해석

이 문제는 예전에 풀어봤던 2696번 중앙값 구하기 https://www.acmicpc.net/problem/2696 이것과 같은 문제이다.

 

아이디어는 이렇다.

우선순위큐 두개를 선언하는데 하나는 오름차순 하나는 내림차순으로 한다.

 

항상 왼쪽 우선순위 큐 내의 모든숫자의 숫자는 중앙 값보다 작은 값이 

오른쪽 우선순위 큐 내의 모든숫자는 중앙 값보다 크게 조절을 하자

 

입력을 받을 때 마다 입력값과 왼쪽 pq의 최댓 값 오른쪽pq의 최솟 값을 비교하여 조절 한 후 중앙값을 출력하면 된다.

 

 

코드

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
priority_queue <int> pq1;
priority_queue < int, vector<int>, greater<int> > pq2;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,input,mid; cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>input;
        if(i==1)
        {
            mid=input;
        }
        else if(i==2)
        {
            if(mid<input)
            {
                pq2.push(input);
            }
            else
            {
                pq2.push(mid);
                mid=input;
            }
        }
        else
        {
            if(mid<input)
            {
                pq2.push(input);
            }
            else
            {
                pq1.push(input);
            }
            if(i&1)
            {
                if(pq1.size()<pq2.size())
                {
                    while(pq1.size()!=pq2.size())
                    {
                        pq1.push(mid);
                        mid=pq2.top();
                        pq2.pop();
                    }
                }
            }
            else
            {
                if(pq1.size()==pq2.size()+1)
                {
                    pq2.push(mid);
                    mid=pq1.top();
                    pq1.pop();
                }
            }
        }
        cout<<mid<<"\n";
    }
}