[백준] 1655번 - 가운데를 말해요 (c++)

백준의 자료구조 문제들을 풀다가 조금 응용이 필요해서 어려운 문제를 발견했다.

풀이가 흥미롭고 좋은 내용이기도 해서 정리해보려 한다.

자료구조 문제들에는 좋은 문제들이 많은 것 같다.

 

문제를 읽고 힙을 이용해야하는 것 같아서 힙을 이용해 풀긴 했다.

문제를 볼 때부터 시간 제한이 0.1초로 빡센게 느낌이 쎄했는데,

역시나 시간초과로 문제를 틀렸다.

 

푼 내용 자체는 틀린것같진 않은데 시간 제한에서 걸린 것 같았다.

어떤 풀이를 이용해 풀어야할지 감이 안잡혀서 구글링을 통해 다른 사람의 풀이를 참고해보았다.

 

풀이가 정말 흥미로웠다.

아래에서 설명해보겠다.

 

 

<문제>

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

1655번: 가운데를 말해요

 

 

 

<시간초과 내 풀이>

#include<bits/stdc++.h>
using namespace std;

void sayMid(priority_queue<int> pq){
    int psize = pq.size(), mid, i = 1, result = 10001;
    if(psize % 2 == 0) mid = psize / 2;
    else mid = psize / 2 + 1;

    while(!pq.empty()){
        if(i < mid) pq.pop();
        else {
            result = min(result, pq.top());
            if(psize % 2 != 0 && i == mid) break;
            else if(i == mid + 1) break;
            pq.pop();
        }
        i++;
    }
    cout<<result<<'\n';
}

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

    int n;
    cin>>n;
    priority_queue<int> pq;

    for(int i=0; i<n; i++){
        int x;
        cin>>x;
        pq.push(x);
        sayMid(pq);
    }
}

처음 내가 풀은 풀이는 위와 같다.

수를 받을 때마다 최대힙에 넣어서 중간값을 그 때마다 구했다.

테스트케이스의 결과는 맞게 나왔지만, 이 방법은 시간초과로 틀렸다.

 

 

 

<다른 사람 풀이를 참고하여 맞은 풀이>

#include<bits/stdc++.h>
using namespace std;

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

    int n;
    cin>>n;
    vector<int> v(n);
    priority_queue<int> max_pq;
    priority_queue<int, vector<int>, greater<int>> min_pq;

    for(int i=0; i<n; i++) cin>>v[i];
    
    for(int i=0; i<n; i++){
        if(max_pq.size() > min_pq.size()) min_pq.push(v[i]);
        else max_pq.push(v[i]);

        if(!max_pq.empty() && !min_pq.empty()){
            if(max_pq.top() > min_pq.top()){
                int a = max_pq.top(); max_pq.pop();
                int b = min_pq.top(); min_pq.pop();
                
                max_pq.push(b);
                min_pq.push(a);
            }
        }
        cout<<max_pq.top()<<'\n';
    }
}

위의 코드는 priority_queue를 이용하여 풀었다.

어떤 풀이로 풀었는지 아래 설명을 보자.

 

먼저 2개의 힙(최대힙, 최소힙)을 사용해서 문제를 해결할 수 있다.

최댓값이 가장 top에 위치하게 되는 최대힙과

최솟값이 가장 top에 위치하게 되는 최소힙으로 중간값을 찾을 수 있다.

 

이 때 2개의 규칙을 따르면서 push를 해야한다.

1) 최대힙의 크기는 항상 최소힙의 크기보다 같거나 1만큼 더 크다.

2) 최소힙의 모든 원소는 최대힙의 모든 원소보다 항상 같거나 커야 한다.

즉, 최소힙의 top() 값이 항상 최대힙의 top() 값보다 항상 같거나 커야한다.

 

백준의 테스트케이스에 나온 {1, 5, 2, 10, -99, 7, 5} 를 삽입하는 과정을 통해 알아보자.

 

첫번째 숫자는 1 현재 최대힙의 크기(0) = 최소힙의 크기(0) 이다. 최소힙에 삽입하면 최소힙의 크기가 더커지므로 규칙 1번에 어긋난다. 규칙 1번에 따라 최대힙에 삽입해야한다. --> 최대힙 = {1}, 최소힙 = { }

두번째 숫자는 5 현재 최대힙의 크기(1) > 최소힙의 크기(0) 이다. 최대힙에 삽입하면 최소힙의 크기보다 2만큼 더 커지기 때문에 규칙 1번에 어긋난다. 규칙 1번에 따라 최소힙에 삽입해야한다. --> 최대힙 = {1}, 최소힙 = {5}

세번째 숫자는 2 현재 최대힙의 크기(1) = 최소힙의 크기(1)이다. 최소힙에 삽입하면 최소힙의 크기가 더커지므로 규칙 1번에 어긋난다. 규칙 1번에 따라 최대힙에 삽입해야한다. --> 최대힙 = {2, 1} , 최소힙 = {5}

네번째 숫자는 10 현재 최대힙의 크기(2) > 최소힙의 크기(1)이다. 규칙 1번을 따라 최소힙에 삽입을 해준다. 규칙 2도 위반하지 않는다(2 < 5). --> 최대힙 = {2, 1} , 최소힙 = {5, 10}

다섯번째 숫자는 -99 규칙 1번을 따라서 최대힙에 삽입을 해준다. --> 최대힙 = {2, 1, -99}, 최소힙 = {5, 10}

여섯번째 숫자는 7 규칙 1번을 따라서 최소힙에 삽입을 해준다. 규칙2도 위반하지 않는다(2< 5). --> 최대힙 = {2, 1, -99}, 최소힙 = {5, 7, 10}

마지막 숫자는 5 규칙 1번을 따라서 최대힙에 삽입해준다. 규칙 2도 위반하지 않는다.(5 = 5) --> 최대힙 = {5, 2, 1, -99}, 최소힙 = {5, 7, 10}

위의 과정에서 최대힙의 각 top() 값들이 중간값을 나타낸다.

 

 

그리고 만약, 규칙 2를 위반하게 될 경우에는

최대힙의 top()값과 최소힙의 top()값을 swap 해줘야한다.

 

예를 들어 {1, -1}을 삽입하는 과정을 보자.

답은 1, -1을 순차적으로 출력해야한다.

위 과정에 따르면 최대힙에 1을 삽입하고 그 후에 최소힙에 -1을 삽입한다.

그런데 이는 규칙 2를 위반하게된다.(1>-1)

그래서 이때는 각 힙의 top()값인 1과 -1을 swap해주어야 한다.

그 후에 최대힙의 top()값을 출력하면 그게 중간값이 된다.