295. Find Median from Data Stream java 풀이

굉장히 오래 헤맨 문제

Node 로 푸는건가 PQ로 푸는건가 했는데 PQ 로 풀면 구할 수 있었다.

 

리밸런싱과 값 처리만 할줄 알면 된다.

 

이걸 근데 코테중에 떠올릴 수 있을지는 모르겠다.

 

class MedianFinder {
    // PQ 두개
    PriorityQueue<Integer> lower; // 작은 값들을 가지고 있을 큐 -> 내림차순
    PriorityQueue<Integer> upper; // 큰 값들을 가지고 있을 큐

    // 둘의 크기가 일정하게 유지되면 된다.
        // 크기를 맞춰서 안맞으면 하나 뺴서 하나 넣고 구하면 가운데를 구할 수 있음

    public MedianFinder() {
        lower = new PriorityQueue<>(Comparator.reverseOrder());
        upper = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        // 일단 없으면 여기부터 넣는다.
        // lower 의 최대값보다 작거나 같은 경우
        if(lower.size() == 0 || num <= lower.peek()) { 
            lower.offer(num); // 작은거니까 넣어주면 된다.
        } else {
            // 그러면 upper 에 넣어준다.
            upper.offer(num);
        }

        // 근데 크기가 일정하게 유지되어야 한다.
        // 리밸런싱
        // 2개 이상 차이나는 경우 옮겨준다.
        if(lower.size() > upper.size()+1) {
            int move = lower.remove();
            upper.offer(move);
        } else if(upper.size() > lower.size() + 1) {
            int move = upper.remove();
            lower.offer(move);
        }
    }
    
    public double findMedian() {
        int maxSize = lower.size() + upper.size();

        if(maxSize % 2 == 0) {
            // 이러면 이제 짝수개
            int sum = lower.peek() + upper.peek();
            return (double)sum/2;
        } else if(lower.size() > upper.size()) {
            return lower.peek();
        } else {
            return upper.peek();
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */