[LeetCode] 933. 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.

 

📌 문제 요약

최근 3000밀리초 안에 들어온 요청의 수를 반환해야 함. (RecentCounter 클래스)
예를 들어, 현재 시간이 5000밀리초라면, 최근 3000밀리초인 2001~5000 사이 들어온 요청만 세야 합니다.
 
 
구현해야 하는 메소드

• RecentCounter() : 최근 요청 수를 0으로 초기화
• ping(int t) : 새로운 요청이 특정 시간 t에 들어올 때 호출 & 최근 3000밀리초 동안 들어온 요청 수 반환

예를 들어,
첫 번째 요청이 시간 t=1에 왔다면, ping(1) 호출 → 범위 : -2999~1, 요청 : [1]
두 번째 요청이 시간 t=100에 왔다면 ping(100) 호출 → 범위 : -2900~100, 요청 : [1, 100]
두 번째 요청이 시간 t=3001에 왔다면 ping(3001) 호출 → 범위 : 1~3001, 요청 [1,100,3001]
세 번째 요청이 시간 t=4000에 왔다면 ping(4000) 호출 → 범위 : 1000~4000, 요청 : [3001,4000]
 
 

💡 풀이 포인트

큐를 활용해 최근 3000밀리초 이내 요청만 유지해야 함.
큐에 요청을 추가한 후 범위를 벗어난 오래된 요청은 큐에서 제거해야 함.
 
 

✅ 풀이 방법

단계

1. 요청 시간 저장할 큐 생성 (큐 초기화)
2. 새로운 요청 시간(t)을 큐에 추가
3. 큐의 맨 앞 요소가 t에서 3000밀리초 이전보다 작으면 범위를 벗어난 것이기 때문에 poll
4. 1~3 반복하여 항상 최근 3000밀리초 이내의 요청만 큐에 남김.
5. 최종 큐의 크기 반환

 
제거와 추가 조건

1. poll : 큐 맨 앞 요소가 t-3000 보다 작은 경우 (= 최근 3000밀리초 범위 벗어난 경우)
2. push : 새로운 요청(t) (= 항상 현재 시점이므로)

 
 

🔎 시간 복잡도

각 원소는 최대 한 번씩만 큐에 들어갔다가 나오기 때문에 평균적인 시간 복잡도는 O(1)
 
→ 각 ping 호출마다 최대 O(n)일 수 있지만(n : ping 호출 수),
모든 호출을 합산했을 때 각 원소가 최대 한 번씩만 들어가고 나가기 때문에 전체적으로 봤을 때 평균 O(1)입니다.
= 각 ping 호출마다 여러 번 제거될 수 있지만 전체적으로 봤을 때 모든 요청이 한 번씩만 추가되고 제거되므로 amortized O(1)
 

🔍 공간 복잡도

최악의 경우에도 큐에는 항상 최근 3000밀리초 내의 요청만 저장되므로 공간 복잡도 O(n)
(n : 최근 3000밀리초 내의 최대 요청 수)
 
 

class RecentCounter {
    Queue<Integer> queue;
    public RecentCounter() {
        queue = new LinkedList();
    }

    public int ping(int t) {
        queue.add(t);
        while (queue.peek() < t - 3000) queue.poll();
        return queue.size();
    }
}