[자료구조] 백준 1655: 가운데를 말해요

1655번: 가운데를 말해요 (acmicpc.net)

1655번: 가운데를 말해요

 

발상의 전환이 필요했다. 솔직히 한 번에 풀지 못했고(테스트케이스는 맞았으나, 시간초과가 남) 다른 사람의 풀이를 구글링하고 난 다음에야 문제를 풀 수 있었다.

 

처음에는, 매 입력마다 list를 정렬하고, 그 가운데 값을 출력하는 간단한 문제로 생각했다. 그러나 이 경우는 매번 전체 리스트를 순회하며 정렬하기 때문에 비효율적이었다.

 

그래서 구글링을 통해 알게 된 발상이, input을 받는 자료구조를 중간점을 기준으로 maxheap, minheap으로 나누어 접근하는 방식이었다. 밑에는 maxheap을 깔고 위에 minheap을 얹어 놓은 구조를 생각해 보자. 이 경우 maxheap이 언제나 minheap보다 그 크기가 같거나 하나 더 크게 하고, minheap의 top이 maxheap보다 언제나 같거나 크게 만들면, maxheap의 top은 언제나 우리가 원하는 중간값을 나타낸다.

 

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin>>N;

    priority_queue<int> maxheap;
    priority_queue<int, vector<int>, greater<int>> minheap;

    int input;

    for(int i=0;i<N;i++)
    {
        cin>>input;

        //condition 1: maxheap.size()==minheap.size() || maxheap.size()==minheap.size()+1
        if(maxheap.size()<=minheap.size())
        {
            maxheap.push(input);
        }
        else if(maxheap.size()==minheap.size()+1)
        {
            minheap.push(input);
        }

        //condition 2: minheap's top is always equal or greater than maxheap's top        
        if (!minheap.empty() && maxheap.top() > minheap.top()) 
        {
            int maxTop = maxheap.top();
            int minTop = minheap.top();
            maxheap.pop();
            minheap.pop();
            maxheap.push(minTop);
            minheap.push(maxTop);
        }      
        cout<<maxheap.top()<<'\n';
    }
}

 

이 블로그의 다른 포스팅에도 heap을 정리하였고, 내가 개인적으로 하고 있는 프로젝트에서도 heap을 사용하여 쏠쏠히 재미를 보았다. (모든 경우의 수를 시뮬레이션 한 후 가장 결과값이 좋은 케이스 하나만 가져오는 연산. heap을 이용하면 매번 top 값이 최대/최소값을 나타내기에 최대/최소값만 추적하면 되는 경우에 상당히 효율적이다.)

 

그런데 솔직히 나에게, heap 두 개를 엮어서 활용한 이 풀이를 생각해 낼 수 있느냐? 하고 물어보면 아마 아닐 것이다. maxheap도, minheap도 사용해 봤지만 '그 두 개를 엮어서 언제나 maxheap의 top이 중간값을 나타내는 자료구조를 만들어야지!' 하는 발상은 아마 못 했을 것 같다. 이론만 공부하는 것이 아니라 꾸준히 적용하고 또 적용해 보는 것이 필요하다는 것을 느낀다.