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

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

1655번: 가운데를 말해요

이 문제는 숫자가 추가로 저장 될 때마다 저장된 숫자 중 가운데 값을 말하는 문제이다. 주어진 시간이 단 0.1초이므로 sort를 쓰게 되면 무조건 시간초과가 나게 된다.

나는 중간이라는 말을 듣고 최대 힙과 최소 힙을 사용하면 되겠다고 생각했다. 중간값을 최대 힙의 탑으로 정하고 중간값 보다 값이 작으면 최대 힙에 값이 크면 최소 힙에 넣어주고 최소 힙의 탑의 값이 바뀌는 경우 그 값을 최대 힙에 넣어주고 팝해주는 형식으로 짰다.

위 처럼 1 7 5가 순차적으로 들어온다고 했을 때, 출력값은 1 1 5 로 맞는 알고리즘 처럼 보인다. 하지만 연속적으로 중간값보다 크거나 작은 값이 오는 경우 (ex 1 2 3 4 5) 다른 값을 내놓게 된다. 여기서 한 2시간 정도 혼자 고민하다 결국 풀이를 봤다...

 

우리가 찾는 값은 결국 중간에 오는 값으로 최대 힙과 최소 힙의 크기에 주목할 필요가 있다.

문제에서 짝수 일 경우 중간값들 중 작은 값을 출력하라고 하였으므로 최대 힙의 루트노드를 중간값으로 기준으로 잡는다.(만약 문제와 다르게 짝수일 경우 중간값들 중 큰 값을 출력해야 한다면 최소 힙의 루트노드를 중간값으로 잡아야 한다)  중간값 보다 값이 작으면 최대 힙에 값이 크면 최소 힙에 넣어주면 되는데 최대 힙의 루트노드가 중간에 위치 할 수 있게 항상 최대 힙의 크기가 최소 힙의 크기보다 같거나 1보다 크도록 유지하게 해줘야 한다.

 

예외 1) 최대 힙의 크기 == 최소 힙의 크기+1 인데 중간값 보다 작은 값이 오는 경우

위의 경우는 잘못 된 경우, 아래의 경우가 맞는 경우이다.

-1은 중간값 3보다 작으므로 최대 힙에 들어가야 하는데 그렇게 하게 되면 중간값이 바뀌지 않는다. 따라서 최대 힙의 루트노드를 최소 힙에 넣어주고 제거하는 과정을 추가해 주어야 한다.

 

예외 2) 최대 힙의 크기 == 최소 힙의 크기 인데 중간값 보다 큰 값이 오는 경우

위의 경우는 잘못 된 경우, 아래의 경우가 맞는 경우이다.

7은 중간값 보다 크기 때문에 최소 힙에 들어가야 하지만 그러면 중간값이 바뀌지 않는다. 따라서 최소 힙의 루트노드를 최대 힙에 넣어주고 제거하는 과정을 추가해야 한다.

 

코드

#include <iostream>

#include <queue>

#include <functional>

using namespace std;

 

priority_queue<int,vector<int>,greater<int> > min_heap;

priority_queue<int,vector<int>,less<int> > max_heap;

int main(){

    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);

    int N,x;

    cin>>N;

    cin>>x;

    cout<<x<<'\n';

    max_heap.push(x);

    for(int i=0;i<N-1;i++){

        cin>>x;

        if(max_heap.size()==min_heap.size()+1){//무조건 min_heap에 넣어주어야 한다.

            if(x<max_heap.top()){

                //예외 1번의 경우

                int tmp=max_heap.top();

                max_heap.pop();

                max_heap.push(x);

                min_heap.push(tmp);

            }else{

                min_heap.push(x);

            }

        }else{//무조건 max_heap에 넣어주어야 한다.

            if(x>min_heap.top()){

                //예외 2번의 경우

                int tmp=min_heap.top();

                min_heap.pop();

                min_heap.push(x);

                max_heap.push(tmp);

            }else{

                max_heap.push(x);

            }

        }

        cout<<max_heap.top()<<'\n';

    }

    return 0;

}