<Hard> Find Median from Data Stream (LeetCode : C#)

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

📕 문제 설명

다음의 함수들이 있을 때 각 함수들 구현하기

MedianFinder() : MedianFinder 초기화
void addNum(int num) : data 추가
double findMedian() : 현재 data에 대한 median 반환

• Input
  함수 실행 정보, 매개변수 정보
• Output
  함수 실행 결과 (구현은 함수를 구현!)

예제

시도 1.

그냥 클래스 생성하기 + median 찾기 구현했는데 sort 하는 부분때문에 19번째 케이스에서 time limit에 걸렸다.

public class MedianFinder {
    List<int> dataList;
    public MedianFinder() 
    {
        dataList = new List<int>();
    }
    
    public void AddNum(int num) 
    {
        dataList.Add(num);
    }
    
    public double FindMedian() 
    {
        int n = dataList.Count;
        dataList.Sort();

        if (n % 2 == 0)
        {
            return (double) (dataList[n/2 - 1] + dataList[n/2]) / 2;
        }
        else
        {
            return (double) dataList[n/2];
        }
    }
}

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

풀이 1.

binary search로 새로운거 추가될 때 위치에 맞게 넣어줘서 매번 정렬하는 것보다 효율성 더 챙길 수 있도록 변경

public class MedianFinder {
    List<int> dataList;
    public MedianFinder() 
    {
        dataList = new List<int>();
    }
    
    public void AddNum(int num) 
    {
        int start = 0;
        int end = dataList.Count - 1;
        int mid = 0;

        while(start <= end)
        {
            mid = (start + end) / 2;

            if (dataList[mid] == num) // 같은 거 있으면 mid에 바로 넣기
            {
                dataList.Insert(mid, num);
                return;
            }
            else if(dataList[mid] <= num) // 들어올 값이 중간보다 크면 
            {
                start = mid + 1;
            }
            else // 들어올 값이 중간보다 작으면 
            {
                end = mid - 1;
            }

        }
        dataList.Insert(start, num);   
    }
    
    public double FindMedian() 
    {
        int n = dataList.Count;

        if (n % 2 == 0)
        {
            return (double) (dataList[n/2 - 1] + dataList[n/2]) / 2;
        }
        else
        {
            return (double) dataList[n/2];
        }
    }
}

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

결과 1.

풀이 2.

우선 순위 큐를 쓰는 풀이. 중간을 기점으로 더 작은 것에서 제일 큰 값과 큰 것에서 제일 작은 값을 뽑으면 median을 구할 수 있다.

public class MedianFinder
{
    PriorityQueue<int, int> lowerHalf; // mid 보다 작은
    PriorityQueue<int, int> higherHalf; // mid 보다 큰 

    public MedianFinder()
    {
        lowerHalf = new PriorityQueue<int, int>();
        higherHalf = new PriorityQueue<int, int>();
    }

    public void AddNum(int num)
    {
        double median = FindMedian();
        if (num > median)
        {
            higherHalf.Enqueue(num, num); // minHeap (최소가 뽑히게)
        }
        else
        {
            lowerHalf.Enqueue(num, -num); // maxHeap (부호 거꾸로 해서 최대가 뽑히게)
        }
        // 두 우선순위 큐 사이즈 맞추는 작업 (동등하게 분배되어야 하므로) => 크기 2개 이상 차이나는 경우 옮기는 작업
        var balanceFactor = higherHalf.Count - lowerHalf.Count;
        if (balanceFactor < 0) // lowerHalf가 사이즈 더 큰 경우
        {
            int moved = lowerHalf.Dequeue();
            higherHalf.Enqueue(moved, moved); // higher로 옮긴다
        }

        if (balanceFactor > 1) // higherHalf가 사이즈 더 큰 경우
        {
            int moved = higherHalf.Dequeue();
            lowerHalf.Enqueue(moved, -moved); // lower로 옮긴다 
        }
    }

    public double FindMedian()
    {
        int count = lowerHalf.Count + higherHalf.Count;
        if (count == 0) return 0;
        if (count % 2 == 0)
        {
            return ((double)lowerHalf.Peek() + higherHalf.Peek()) / 2;
        }
        else
        {
            return higherHalf.Peek();
        }
    }
}

결과 2.