[LeetCode] Number of Recent Calls

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:
RecentCounter() Initializes the counter with zero recent requests.
int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). 

Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].
It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

Example 1:
Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]

Explanation
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1], range is [-2999,1], return 1
recentCounter.ping(100);   // requests = [1, 100], range is [-2900,100], return 2
recentCounter.ping(3001);  // requests = [1, 100, 3001], range is [1,3001], return 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002], range is [2,3002], return 3
 

Constraints:
1 <= t <= 109
Each test case will call ping with strictly increasing values of t.
At most 104 calls will be made to ping.

---

RecetnCounter 클래스를 구현하는 문제.

최근 요청 수는 0으로 초기화된다.

함수 ping(int t)은 새로운 요청을 t 시간(ms)에 추가하고,

이번에 추가된 요청을 포함하여 지난 3000ms동안 들어온 요청 수를 리턴한다. (t-3000~ t)

모든 ping 함수의 호출은 이전 호출보다 반드시 t값이 더 크다고 보장된다.

 

var RecentCounter = function() {
    this.requests = [];
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
    this.requests.push(t);
    const past = t - 3000; // current == t
    let cnt = 0;
    for(const ping of this.requests){
        if(ping <= t && past <= ping){
            cnt ++;
        }
        if(t < ping){
            break;
        }
    }
    return cnt;
};

단순히 그냥 requests를 담는 필드를 만들고,

ping을 호출할 때마다 길이를 최근 3000ms 이내에 호출된 요청이면 cnt를 1씩 올리고 cnt를 리턴한다.

 

RecentCounter.prototype.ping = function(t) {
    this.requests.push(t);
    const past = t - 3000; // current == t
    for(let i=0; i < this.requests.length; i++){
        // 끝까지 돌 필요가 없다.
        if(past <= this.requests[i]){
            return this.requests.length - i;
        }
    }
};

근데 생각해 보니 끝까지 돌 필요가 없어서 이렇게 또 개선해 보고...

 

또 생각해 보니 모든 요청 시간을 보관해야할 필요가 없다면... 

RecentCounter.prototype.ping = function(t) {
    this.requests.push(t);
    const past = t - 3000; // current == t
    for(let i=0; i<this.requests.length; i++){
        // 끝까지 돌 필요가 없다.
        // 모든 요청을 보관할 필요가 없다면?
        if(past <= this.requests[i]){
            this.requests = this.requests.splice(i, this.requests.length);
            return this.requests.length;
        }
    }
};

이렇게 할 수도 있다.

 

근데? 꼭 splice로 자를 필요가 없다.

그렇게 되면 배열 자체를 교체를 해버리는 거라..

클래스 구현인 걸 감안하면 다른 데서 참조하고 있을 수도 있으니 좀 별로기도 하고.

 

좀 더 직관적으로 하려면 그냥 shift로 날려 버리는 게 나을 듯 싶다.

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

이렇게 ~_~

 

하지만 만약 지금까지 들어온 모든 요청을 보존은 해야한다면?

function RecentCounter() {
    this.requests = [];
    this.start = 0; // 유효한 범위의 시작 인덱스
}

RecentCounter.prototype.ping = function(t) {
    this.requests.push(t);
    const past = t - 3000;

    // start 인덱스를 앞으로 이동
    while (this.requests[this.start] < past) {
        this.start++;
    }

    return this.requests.length - this.start;
};

3000ms 이내의 요청 시작 위치를 나타내는 start라는 필드를 추가하고,

매번 ping을 호출할 때마다 start 위치를 갱신해 주는 식으로 해도 된다~