[ 백준 / C++ ] 1655 : 가운데를 말해요

[ 문제 ]

 

1655번: 가운데를 말해요

 

[ 접근방법 ]

 

2개의 우선순위 큐를 통해 O(n log n) 으로 문제를 해결한다.

 

leftQ는 제일 큰 값이 top에 배치되고, rightQ는 제일 작은 값이 top에 배치되도록 설정했다.

 

leftQ가 rightQ와 같거나 딱 한 개의 값이 더 많도록 세팅하고 있으므로, 중간값은 무조건 leftQ의 top이다.

파란색 : leftQ , 초록색 : rightQ

 

정리하자면, 입력들을 정렬했을 때 중간값 포함 왼쪽 묶음을 leftQ에 넣고 나머지 오른쪽 묶음을 rightQ에 넣는다.

 

[ 소스코드 ]

 

#include <iostream>
#include <queue>

using namespace std;

int n;
priority_queue<int> leftQ;
priority_queue<int, vector<int>, greater<int>> rightQ;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    while(n--){
        int cnt; cin >> cnt;

        if(leftQ.size() == rightQ.size())leftQ.push(cnt);
        else rightQ.push(cnt);

        if(!rightQ.empty() && leftQ.top() > rightQ.top()){
            int lt = leftQ.top(); leftQ.pop();
            int rt = rightQ.top(); rightQ.pop();

            leftQ.push(rt);
            rightQ.push(lt);
        }

        cout << leftQ.top() << "\n";
    }

    return 0;
}