백준 1655 가운데를 말해요 : 우선순위 큐 두개로 가운데를 빠르게 c++

문제 링크

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

1655번: 가운데를 말해요

풀이 아이디어

이 문제는 오직 '가운데' 에 무엇이 있냐만 관심이 있는 문제이다.

만약 이 문제를 입력이 들어올때마다 정렬해서 가운데 인덱스의 원소를 출력하려고 하면 nlogn의 시간이 걸린다.

1부터 100000까지의 입력이 들어온다고 가정할때 합치면 약 1700초의 시간이 걸리는 무식한 방법이므로 이 방법은 쓸 수 없다.

즉 아예 들어올때마다 '정렬'을 통해서 무언가를 하려고 하면 안된다는 사실을 먼저 인지하자.

 

이 문제는 nlogn의 구원자, priority queue를 2개를 활용하면 풀 수 있다.

minQ와 maxQ 두 개의 priority queue를 우선 준비한다.

N개의 원소가 있고 그 중 n개의 숫자까지 진행되었다고 가정했을때,

minQ에는 크기별로 0~mid의 작은 원소들이, maxQ에는 mid+1~n 의 큰 원소들이 들어가는 우선순위 큐이다.

즉 minQ의 가장 큰 수 는 maxQ의 가장 작은 수보다 작아야 된다.

 

이를 구현하려면 minQ는 가장 큰 수가 top()에 위치하도록 cmp 인자를 less<int>로 주고,

반대로 maxQ는 가장 작은 수가 top()에 위치하도록 greater<int> 로 인자를 준다.

 

그 후는 간단하다. minQ - maxQ - minQ - maxQ -... 의 패턴으로 원소가 들어오도록 for문을 돌린 후, 

minQ의 최댓값과 maxQ의 최솟값의 대소관계를 비교하면서 대소관계가 역전될경우, top 원소를 바꾸기만 하면 된다.

#include <bits/stdc++.h>
using namespace std;
int N;
priority_queue<int,vector<int>,less<int>> minQ; //4321
priority_queue<int,vector<int>,greater<int>> maxQ; //1234
 
 
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>N;
    for(int i=0; i<N; i++) {
        int num;
        cin >> num;
        if(minQ.size()==maxQ.size())
            minQ.push(num);
        else
            maxQ.push(num);
 
        if(i==0)
            cout<<minQ.top()<<"\n";
        else {
            int a = minQ.top();
            int b = maxQ.top();
            if (a > b) {
                minQ.pop();
                maxQ.pop();
                minQ.push(b);
                maxQ.push(a);
            }
            cout<<minQ.top()<<"\n";
        }
    }
}