Leetcode - 933. Number of Recent Calls

문제

ping()이 특정 시간 t 마다 호출된다.(단위 msec) 매번 ping이 호출 될때마다 최근 3000 msec 동안 호출된 ping의 갯수를 구하라. (t는 증가하기만 할수있다)

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

해결 아이디어

• 슬라이딩 윈도우
  처음에 배열에 left right변수를 사용해서 구현하려고 했는데, 공간복잡도가 비효율적이고, 인덱스 계산도 복잡해서 실패.
• queue 이용

(1) --- (100) --- (3001) --- (3002)

(3002) 가 들어오면 1은 3002 - 3000 보다 작기 때문에 (1)은 queue에서 제거한다. 조건이 맞을때까지 반복해서 제거. 그리고 마지막에 큐의 사이즈를 리턴하면 아주 간단하게 구현할 수 있다.

무척 좋은 문제라고 생각함!

풀이

풀이가 놀랍도록 심플..!

class RecentCounter {
public:
    queue<int> history;

    RecentCounter() {
    }
    
    int ping(int t) {
        history.push(t);
        while (history.front() < t - 3000)
            history.pop();
        return history.size();
    }
}