Data Stream as Disjoint Intervals

Data Stream as Disjoint Intervals

문제 내용

Class 를 만드는 문제이다.

Class의 목표는 다음과 같다.

• addNum(int) : integer를 입력 받는다
• getIntervals() : 입력받은 integer의 배열이 1의 차이로 연결되어 있다면 [start,end]로 연결되어 있는 값의 시작값과 연결이 끝나는 끊값으로 구성된 2차원 배열을 return 한다.

 

접근 방법

해당 문제는 다음과 같은 constraints를 갖는다.

• $ 0 <= val <= 10^4 $

즉, val은 최대 10000개까지 밖에 운영 되지 않는다.

이정도면 큰 값이 되지 않기 때문에 array로 cover 가능하다. 

우선 Brute force로 해당 문제를 해결해 보자.

var SummaryRanges = function() {
    this.arr = new Array(10001).fill(false);
};

/**
 * @param {number} val
 * @return {void}
 */
SummaryRanges.prototype.addNum = function(val) {
    this.arr[val] = true;
};

/**
 * @return {number[][]}
 */
SummaryRanges.prototype.getIntervals = function() {
    const result = new Array();

    let flag = false;
    let startIdx = -1;

    for(let i = 0; i < 10001; i++){
        if(this.arr[i]){
            if(!flag){
                startIdx = i;
                flag = true;
            }
        } else {
            if(flag){
                result.push([startIdx,i-1]);
                flag = false;
            }
        }
    }

    return result;
};

위의 코드를 보면 array를 10001로 설정하고 있는데 그 이유는 입력 값에 10001이 절대 들어오지 않기 때문에 loop를 종료 시키는 처리를 쉽게 할 수 있기 때문이다.

10001개의 array를 false로 만들어 두고, 가장 왼쪽 0부터 100001번까지 순차적으로 start인지 end인지를 flag로 check하면서 결과 값에 array를 push해주면 된다.

Time complexity로 보자면, getIntevals는 $ O(1) $ 이된다. Constant Time인데 그 이유는 loop가 10001개로 고정되었기 때문이다.  하지만 실제 속도를 보자면 $ O(N) $ 이라고 보는 것이 타당하다.

 

Range Memorization

이것을 조금더 개선해 볼수 없을까?

각 index의 value값을 true, false말고 마지막 값으로 연결해 보자.

예를 들자면 아래와 그림과 같이 작동하게 해보자.

10000개의 index와 각 index 값을 -1로 지정했다.

2를 넣어 주고 해당 위치에 2의 값을 표시해 준다.

3을 넣어주고 만약 뒷쪽에 연결되는 값이 있다면 현재 자신의 값으로 업데이트 시켜준다.

1을 넣었을 때 뒤에 인접한 값이 있다면 자신의 값을 인접한 뒤 cell의 값으로 업데이트 시켜준다.

이런 방법으로 12의 값도 업데이트 가능하다.

정리해보자면 다음과 같다.

• 0 < arr[idx + 1] then arr[idx] = arr[idx -1]
• while 0 < arr[idx - 1] then arr[idx-1] = arr[idx]

코드로는 다음과 같다.

var SummaryRanges = function() {
    this.arr = new Array(10001).fill(-1);
};

/**
 * @param {number} val
 * @return {void}
 */
SummaryRanges.prototype.addNum = function(val) {
    if(0 <= this.arr[val]) return;

    this.arr[val] = val;

    if(0 < this.arr[val + 1]){
        this.arr[val] = this.arr[val+1];
    }

    while(0 < val && 0 <= this.arr[val-1]) this.arr[val-1] = this.arr[val--];
};

/**
 * @return {number[][]}
 */
SummaryRanges.prototype.getIntervals = function() {
    const result = new Array();

    for(let i = 0; i < 10001; i++){
        if(0 <= this.arr[i]){
            result.push([i, this.arr[i]]);
            i = this.arr[i] + 1;
        }
    }

    return result;
};

time complexity는 여전히 $ O(N) $ 이지만 속도에 증가를 보인다.

여기에 반대쪽 Memorization을 추가하면 하기에 보여줄  Binary search를 사용하는 방법과 준하는 속도를 보여준다.

역방향 Memory를 추가한 모습이다.

이것을 코드로 추가하면 아래와 같다.

var SummaryRanges = function() {
    this.arr = new Array(10001).fill(-1);
    this.re = new Array(10001).fill(10000);
};

/**
 * @param {number} val
 * @return {void}
 */
SummaryRanges.prototype.addNum = function(val) {
    if(0 <= this.arr[val]) return;

    this.arr[val] = val;

    if(0 < this.arr[val + 1]){
        this.arr[val] = this.arr[val+1];
    }

    while(0 < val && 0 <= this.arr[val-1]) this.arr[val-1] = this.arr[val--];
    const lastIdx = --val;
    while(0 <= val && this.arr[val] < 0) this.re[val--] = lastIdx;
};

/**
 * @return {number[][]}
 */
SummaryRanges.prototype.getIntervals = function() {
    const result = new Array();

    for(let i = 0; i < 10001; i++){
        if(0 <= this.arr[i]){
            result.push([i, this.arr[i]]);
            i = this.arr[i] + 1;
        } else {
            i = this.re[i];
        }
    }

    return result;
};

여전히 $ O(N) $ 이지만 getIntervals의 속도가 $ O(grouping 갯수) $ 의 속도로 빨라진다.

 

Binary Search (Heap)

위와 속도는 거의 비슷하지만 Memory를 줄이는 방법이 있다.

결국 위의 getIntervals에서 필요한건 sorting이 된 value의 array라는 점에서 착안한 것이다.

즉, [2,5,7] 이 있으면 3번 loop를 돌아서 결과 값을 얻을 수 있다. 여기에 3이 들어가면 [2,3,5,7] 이런 순서에 맞는 value array를 구하는게 핵심이다.

가장 쉽게 이러한 insertion 행위가 가능한 것은 Binary Search이다.

예를 들어서 [2,5,7]에서 3이 들어갈 자리는

2와 5사이 이다 이 Position을 가장 빠르게 찾는 방법은 Lower Bound를 찾는 것이다.

2021.06.16 - [Problem Solving] - Binary Search Lower Bound와 Upper Bound

상기 내용에서 Lower bound를 꼭 읽어보자.

해당 코드는 아래와 같다.

var SummaryRanges = function() {
    this.arr = new Array();
};

/**
 * @param {number} val
 * @return {void}
 */
SummaryRanges.prototype.addNum = function(val) {
    if(this.arr.length === 0) {
        this.arr.push(val);
        return;
    }

    let left = 0;
    let right = this.arr.length;

    while(left < right){//1
        const mid = left + Math.floor((right - left)/2);

        if(this.arr[mid] === val){
            return;
        }

        if(val < this.arr[mid]){
            right = mid;
        } else {
            left = mid + 1;
        }

    }

    this.arr.splice(left, 0, val);
};

/**
 * @return {number[][]}
 */
SummaryRanges.prototype.getIntervals = function() {
    const result = new Array();

    let start = this.arr[0];
    let end = this.arr[0];

    for(let i = 1; i < this.arr.length; i++){
        if(1 < this.arr[i] - end) {
            result.push([start,end]);
            start = this.arr[i];
            end = this.arr[i];
        } else {
            end = this.arr[i];
        }
    }

    result.push([start,end]);


    return result;
};

add Num의 $ O(logN) $ 으로 빨라지게 된다.

이와 같이 순서를 유지하면서 Next 값을 얻을 수 있는 자료구조가 하나더 있다 바로 Heap이다.

Min Heap을 사용하면 바로 다음에 오는 값을 찾을 수 있다.

2020.09.14 - [Problem Solving] - Javascript Priority Queue 오름 차순

위 링크로 설명을 대체하자 

이것도 결론은 $ O(logN) $으로 동일함으로 해당 부분을 추가 개발하진 않았다.