295. Find Median from Data Stream - Streak 2

이번 문제는 다음 자료구조를 완성하라는 문제였다.

 

이런 유형의 문제는 릿코드만의 독특한 알고리즘 문제로, 라이브코테에서 만날 법한 문제였다.

 

가장 먼저 든 생각은 "중간을 찾는 자료구조"를 만드는 것이었다.

두개의 스택을 이용해 큐를 만드는 것처럼,
두 개의 우선순위 큐를 이용해 중간값을 유지하는 MedianFinder 클래스를 구현했다.

class MedianFinder {
    PriorityQueue<Integer> high = new PriorityQueue<>();
    PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
    int count = 0;

    public MedianFinder() {
    }

    public void addNum(int num) {
        /**
        x 보다 크면 위에 삽입
        x보다 작으면 아래에 삽입
        */
        if(count == 0) {
            low.add(num);
        } else if(low.peek() < num) {
            high.add(num);
        } else {
        low.add(num);
        }

        count++;  
        if(low.size() > high.size() + 1) {
            int temp = low.poll();
            high.add(temp);
        } else if(low.size() < high.size()) {
            int temp = high.poll();
            low.add(temp);
        }
    }

    public double findMedian() {
        if (count % 2 == 1){
            return low.peek();
        } else {
            return (double)(low.peek() + high.peek())/2.0;
        }
    }
}



/**

* Your MedianFinder object will be instantiated and called as such:

* MedianFinder obj = new MedianFinder();

* obj.addNum(num);

* double param_2 = obj.findMedian();

*/