[LeetCode] 295. Find Median from Data Stream

문제 출처: https://leetcode.com/problems/find-median-from-data-stream/

Find Median from Data Stream - LeetCode

 

문제

중앙값은 정렬된 정수 배열에서 중간 값을 말한다. 만약 리스트의 크기가 짝수라면, 중간값이 존재하지 않고, 두 중간값의 평균을 계산한다.

• 예를 들어, arr = [2, 3, 4]라면, 중앙값은 3이다.
• 예를 들어, arr = [2, 3]라면, 중앙값은 (2 + 3) / 2 = 2.5이다.

 

MedianFinder 클래스를 구현하라:

• MedainFinder()는 MedianFinder 객체를 초기화한다.
• void addNum(int num)은 데이터 구조에 정수 num을 추가한다.
• double findMedian()은 모든 원소에서 중앙값을 반환한다.

 

예제

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

 

풀이

문제를 보고 처음 떠올린 생각은 정렬을 이용한 방법이었다. 리스트 구조를 이용하여 값을 저장하고, 중앙값을 계산해야 하는 순간에 리스트를 정렬함으로써 중앙 위치의 값이 무엇인지 바로 알게 하는 방법이다.

var MedianFinder = function() {
    this.list = [];
};

MedianFinder.prototype.addNum = function(num) {
    this.list.push(num);
};

MedianFinder.prototype.findMedian = function() {
    let median = null;

    this.list.sort((a, b) => a - b);

    const half = Math.floor(this.list.length / 2);
    if (this.list.length % 2) {
        median = this.list[half];
    } else {
        median = (this.list[half] + this.list[half-1]) / 2;
    }

    return median
};

이 방법은 직관적인 방법이긴 하지만 효율적이지 못한 방법이다. 실제로 런타임 시간이 6768ms로 시간초과에 걸리지 않은게 용할 따름이다.

 

중앙값을 찾기 위해서, 입력되는 값들이 정렬되어야 한다는 사실은 분명하다. 그렇기 때문에 어떤 방식으로 정렬된 배열을 얻어 내느냐가 이 문제의 효율성을 좌우한다고 생각했다.

 

실제로 어떤 방식을 채택해야하는지 감이 오지 않아 다른 사람들의 코드를 참조해보니, 1) 이진탐색트리(BST)를 이용하는 방법 2) Min/Max-Heap을 이용하는 방법 등이 있었다.

 

이진탐색트리를 이용하는 방법의 경우, 이진탐색트리의 특성을 이해하고 있다면 어떤 방식으로 답을 찾고자 하는지 감이 올 것이라 생각한다. 이진탐색트리의 효율성에 대해 생각해보면, O(logn) 시간이 소요될 것을 예상할 수 있다.

 

다음으로 최소/최대 힙을 이용한 방법에 대해서 생각해보자. 이 방법의 경우, 실제로 구현을 하면서 동작 방식을 이해하고자 한다.

 

힙을 최소 또는 최대 힙 중 하나를 선택해서 값을 저장하고 순차적으로 값을 접근하면서 중앙값을 찾아내는 방법도 있겠지만, 여기서는 최소/최대 힙을 모두 활용하는 방안에 대해서 이야기하고자 한다.

 

이 두개의 힙을 어떻게 사용할 것인지 보면, 각각 저장해야 되는 원소 중 절반만을 저장한다. 중앙값 계산 직전 두 힙에 저장되어 있는 데이터의 형태에 대해 생각하면, 최소 힙의 경우 상대적으로 큰 값들이 저장되고, 최대 힙에는 상대적으로 작은 값들이 저장되어 있어야 한다. 이러한 형태로 값들이 저장된다고 하면, 중앙값을 찾는 과정은 각 힙의 top 값을 가져와 연산을 수행하는 것으로 중앙값을 구할 수 있다.

 

관건은 이 두개의 힙을 어떻게 유지시켜야 위에서 언급한 대로 저장되느냐는 것이다. 아래의 코드를 보자.

var MedianFinder = function() {
    this.maxHeap = [];
    this.minHeap = [];
};

MedianFinder.prototype.addNum = function(num) {
    heapPush(this.maxHeap, num);
    heapPush(this.minHeap, -heapPop(this.maxHeap));

    if (this.maxHeap.length < this.minHeap.length) {
        heapPush(this.minHeap, -heapPop(this.maxHeap));
    }
};

우선, 어떤 값이 들어오든 최대 힙에 저장한다. 힙 자료구조의 특성에 의해서 최대 힙 자료구조의 루트 노드에는 현재 들어온 값 중 가장 큰 값이 위치해있을 것이다. 이후, 바로 그 값을 빼내어 최소 힙에 저장한다. 여기까지만 생각한다면, 주어지는 모든 값들은 최소 힙에 저장될 것이고, 최대 힙을 쓰는 의미 또한 불분명하다.

 

다음 조건문을 보자. 최소힙의 크기가 최대힙의 크기보다 크게 되면, 최소힙의 루트 값을 빼내어 최대힙으로 넣는 과정이 작성되어 있다. 이 코드를 통해서 최소힙과 최대힙의 크기는 동일하거나, 최대힙이 최소힙 보다 1 큰 상태로만 유지된다. 그 안의 저장되어 있는 값들 또한 실제적으로 각 힙의 top값을 주고받기 때문에 최소힙에는 최대힙의 top값보다 큰 값들이 저장되고, 최대힙에는 최소힙의 top값보다 작은 값들이 저장된다.

 

이후 중앙값을 계산하는 것은 두 힙의 사이즈에 따라 다음과 같이 계산될 수 있다.

MedianFinder.prototype.findMedian = function() {
    if (this.maxHeap.length == this.minHeap.length) {
        return (this.maxHeap[0] - this.minHeap[0]) / 2;
    } else {
        return this.maxHeap[0];
    }
};

 

Github: 295.js

opwe37/Algorithm-Study