[Heap][Hard] 295. Find Median From Data Stream

Q. 주어진 값들의 중앙값을 반환하는 클래스를 만들어라. 

 이때 중앙값은, 값들의 수가 홀수일때는 가운데 존재하는 값, 

 짝수일때는 가운데 양 옆 두수의 평균을 말한다. 

 

Solution. 

 입력된 수들을 정렬 했을 때, 가운데 지점을 찾아야 한다. 

 따라서 

 

 솔루션 1. 값을 리스트에 계속 추가하고, 가운데 값을 구할 시 정렬하고 중간값을 찾는다. -> 정렬에 O(N x LogN)이 매번 소모된다. 비 효율적이다. 

 

 솔루션 2. map 등의 구조를 사용하여 넣을 시 정렬한다.O(logN) -> 중간값을 찾을 때 위치 순회하는데, O(N/2) 이 소모된다. 나쁘진 않아 보이지만, 더 효율적인 방법을 생각해 본다.

 

 솔루션 3. 두개의 priority queue를 활용해 본다.  

  중간값보다 작은 녀석들은 max heap 에 담는다. 

  중간값보다 큰 녀석들은 min heap에 담는다. O(logN)

  그렇다면 두 자루안의 수가 같으면 각 힙에서의 top 값이 바로 중간 값이 된다. 

  홀수일때는 두 자루 중 더 수가 많은 자루의 top을 취하면 된다.  O(1)

대충 이런 식으로 두개의 힙을 쓴다.

 

 

솔루션 3을 코드로 작성해 본다. 

 

class MedianFinder {
public:

    priority_queue<int,vector<int>,greater<int>> minPQ;
    priority_queue<int> maxPQ; 

    MedianFinder() {
    }
    
    void addNum(int num) 
    {
        if(minPQ.size() > 0)
        {
            if(num > minPQ.top())   minPQ.push(num);
            else                    maxPQ.push(num);
        }
        else 
            maxPQ.push(num);

        if(minPQ.size()+2 == maxPQ.size())
        {
            minPQ.push(maxPQ.top());
            maxPQ.pop();
        }
        else if(minPQ.size() == maxPQ.size()+2)
        {
            maxPQ.push(minPQ.top());
            minPQ.pop();
        }
    }
    
    double findMedian() 
    {
        int total = minPQ.size() + maxPQ.size();
        if(total%2 == 1)
        {
            return minPQ.size()>maxPQ.size() ? minPQ.top() : maxPQ.top();
        }
        else 
        {
            return ((double)(minPQ.top() + maxPQ.top())) / 2.0;
        }
    }
};

 

 

적절한 결과를 얻었다.