리트코드 295. Find Median from Data Stream

https://leetcode.com/problems/find-median-from-data-stream/description/

Find Median from Data Stream - LeetCode

 

힌트 1. 중앙값을 찾는 문제인데, 중앙값이란 원소 개수가 홀수개일 때, 중앙값 x를 기준으로 x보다 작은 값이 n개 x보다 큰 값이 n개인 수이다.

 

힌트 2. 원소 개수가 짝수개일 경우 x보다 작은 원소가 n 개 y보다 큰 원소가 n개인 (x + y) / 2값이 중앙값이 된다.

 

힌트 3. x보다 작은 n개의 수가 담긴 리스트는 원소개수가 n+1개인 max heap의 최댓값이 x일 경우이다.

 

힌트 4. y보다 큰 n개의 수가 담긴 리스트는 원소 개수가 n+1개인 min heap의 최솟값이 y일 경우이다.

 

힌트 5. 위의 명제가 성립하기 위해서는 x<=y이어야만 한다.

 

class MedianFinder {

    private static PriorityQueue<Integer> maxHeap;
    private static PriorityQueue<Integer> minHeap; 
    public MedianFinder() {
        //Heap 초기화
        maxHeap = new PriorityQueue<>((a, b) -> b-a);
        minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {

        // 1. maxHeap과 minHeap에 번갈아가면서 숫자를 채운다
        if(maxHeap.size() == minHeap.size()){
maxHeap.add(num);
        }else{
            minHeap.add(num);
        }
        
        // 2. minHeap의 최솟값은 maxHeap의 최댓값보다 크거나 같아야한다
        if(maxHeap.isEmpty() || minHeap.isEmpty()) return;

        // 2-1. minHeap의 최솟값이 maxHeap의 최댓값보다 작으면 둘의 위치를 바꿔준다.
        while(maxHeap.peek() > minHeap.peek()){
            int tmp = minHeap.poll();
            minHeap.add(maxHeap.poll());
            maxHeap.add(tmp);
        }
    }
    
    public double findMedian() {
        // 3. maxHeap부터 채울 것이므로 maxHeap이 비어있다면 return null;
        if(maxHeap.isEmpty()) return 0.0;

        // 3-1. maxHeap과 minHeap의 사이즈가 같다면 각각의 최대 최소를 뽑아서 2로 나누기
        if(maxHeap.size() == minHeap.size())
        { 
            return (double) (maxHeap.peek() + minHeap.peek()) / 2;
        }// 3-2. maxHeap과 minHeap의 사이즈가 다르다면 maxHeap의 최댓값이 중앙값
        else{
            return (double) maxHeap.peek();

        }

    }
}

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