[LeetCode] 933. Number of Recent Calls 해설 및 풀이 (Python)

LeetCode 933. Number of Recent Calls

https://leetcode.com/problems/number-of-recent-calls/submissions/1617618196/?envType=study-plan-v2&envId=leetcode-75

 

---

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.

 

---

문제 유형

Design Queue Data Stream

 

풀이 방법 도출

 

요청이 발생한 시간 t가 주어지면 t-3000부터 t까지의 구간에 몇 번의 요청이 있었는지를 카운트해야 합니다.

 

 

 

1. deque를 이용해 요청 시간을 저장합니다.
2. 새로운 요청이 들어올 때마다 현재 시점 기준 유효 시간 범위에 속하지 않는 오래된 요청들을 앞에서 제거합니다.
3. deque의 길이 자체가 유효한 요청의 개수가 됩니다.
4. ping을 호출할 때마다 현재 요청 수를 리턴합니다.
5. getMaxCount를 호출하면 지금까지 반환된 요청 수 중 최대값을 반환합니다.

 

 

시간 복잡도

• O(1)

---

핵심 코드 삽입 및 설명

 

from collections import deque

class RecentCounter:
    def __init__(self):
        # 요청 시간을 저장할 deque 생성
        self.requests = deque()
        self.start_time = 0
        self.end_time = 0
        self.count = 0
        self.max_count = 0  # 최대 요청 수 저장

    def ping(self, t: int) -> int:
        # 새로운 요청 시간 t를 큐에 추가
        self.requests.append(t)

        # 유효한 시간 범위
        self.start_time = t - 3000
        self.end_time = t

        # 유효 범위 밖의 오래된 요청은 큐에서 제거
        while self.requests and self.requests[0] < self.start_time:
            self.requests.popleft()

        # 현재 유효한 요청 수 계산
        self.count = len(self.requests)

        # 지금까지의 최대 요청 수 갱신
        self.max_count = max(self.max_count, self.count)

        return self.count
    
    def getMaxCount(self) -> int:
        # 최대 요청 수 반환
        return self.max_count