Number of Recent Calls

Number of Recent Calls

Explore - LeetCode

- 문제 내용 : ping이 들어오면 들어온 시점으로 부터 3000 milliseconds 이전에 몇번의 ping 요청이 왔는지 Count를 출력

- 접근 방법

Array Queue를 이용해서 3000 milliseconds이전의 값은 모두 삭제하고 남아 있는 Length를 return 한다.

var RecentCounter = function() {
    this.queue = new Array();
};

RecentCounter.prototype.ping = function(t) {
    
    if(0 < this.queue.length){
        while(3000 < t - this.queue[0]){
            this.queue.shift();
        }
    }
    
    this.queue.push(t);
    
    return this.queue.length;
};

문제가 easy라서 그렇긴 한다. 사실 위와 같이 문제를 접근하는 것은 좋아 보이진 않는다.

다음과 같이 문제를 확장한다고 생각해봐야 할 것 같다.

• 주어진 ping time에 맞는 전 3000 milliseconds count를 return 하라

달라진 점은 ping time이 선형적으로 늘어나게만 하지 않는 다는 것이다.

예를 들자면 1,3000,5000 이런식이 아니라

1,3000,5000,2 이런식으로 time을 변환 시킬 경우의 대응 방법을 알아야 할 것같다.

이와 같은 문제는 Treemap과 Treeset을 통해서 해결이 가능하다.

해당 부분은 Treemap과 Treeset을 javascript로 개발이 선행 되어야 함으로 다른 포스트를 통해서 설명하고자 한다.