[BOJ #1655] 가운데를 말해요, C++

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

 

[문제 요약]

 

입력으로 N개의 정수가 주어진다. (0 ≦ N ≦ 100,000)

각 정수가 입력될 때마다 이태까지 입력된 정수들의 중간값을 출력해야 한다. 

만약 입력된 정수의 수가 짝수라면, 중간에 있는 두 수중 작은 수를 출력한다. 

 

[문제 풀이]

 

문제 풀이에 정렬에 용이한 우선순위 큐(priority queue)를 사용할 것이다. 

하지만 우선순위 큐에서는 벡터처럼 인덱스를 지정해 접근할 수 없다.

이 문제를 극복하기 위해서 

• 중간값을 포함한 작은 수들을 저장한 우선순위 큐 
• 중간값보다 큰 수들을 저장한 우선순위 큐 (단, 가장 작은 값이 top에 오도록 정렬 방식을 조정해야 함)

이렇게 두 가지를 사용할 것이다! 편의상 small_pq, big_pq 라 지칭하겠다.

위 방식을 사용하면 small.top()에 우리가 출력해야 할 중간값이 위치하게 된다.

 

그렇다면 어떻게 작은 값들과 큰 값들을 분리해서 저장할 수 있을까?

 

psuh 할 때 기본적으로 세 가지의 원칙을 따르면 된다.

1. 짝수번째에 small_pq, 홀수번째에 big_pq에 번갈아가며 push 한다.
2. small_pq에 push할 차례인데 넣을 값이 big.top() 보다 크다면 big.top()의 값을 small_pq로 옮겨주고 입력받은 값을 big_pq에 push 한다.
3. big.pq에 push할 차례인데 넣을 값이 small.top() 보다 크다면 small.top()의 값을 big_pq로 옮겨주고 입력받은 값을 small_pq에 push 한다.

 

[전체 코드]

 

#include <iostream>
#include <queue>

using namespace std;

int N, x, temp;

int main(){
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    cin>>N;
    priority_queue<int> minn;
    priority_queue<int> maxx;
    for(int i=0; i<N; i++){
        cin>>x;
        if(i%2==0){
            if(!minn.empty() && x>minn.top()*-1){
                temp=minn.top()*-1;
                minn.pop();
                maxx.push(temp);
                minn.push(x*-1);
            }
            else maxx.push(x);
        }
        else{
            if(x<maxx.top()){
                temp=maxx.top()*-1;
                maxx.pop();
                minn.push(temp);
                maxx.push(x);
            }
            else minn.push(x*-1);
        }
        cout<<maxx.top()<<'\n';
    }
}

 

 

* 입력되는 수가 많으니 endl 대신 \n 을 사용하도록 하자!