리트코드 - 933. Number of Recent Calls

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

Number of Recent Calls - LeetCode

이 문제는 최근 3000밀리초(ms) 동안 발생한 요청의 수를 계산하는 것이다.

각 ping 호출이 발생할 때마다 새로운 요청이 발생한 시간을 기록하고, 각 호출을 기준으로 3000ms 동안의 요청만을 고려해야 한다.

 

각 요청의 시간을 기록하기 위해 deque 자료구조를 사용했다.

ping 함수가 호출될 때마다, 현재 시간 t를 deque에 추가한다. 그 후, deque의 가장 앞쪽에 있는 요소가 가장 오래된 요청이므로 현재 시간 t로부터 3000ms 이전인 경우, 그 요소를 deque에서 제거한다.

결과적으로 deque에는 항상 최근 3000ms 이내의 요청만이 남게 되며, 시간 범위 내의 요청 수를 반환할 수 있다.

 

from collections import deque
class RecentCounter:

    def __init__(self):
        self.queue = deque()

    def ping(self, t: int) -> int:
        self.queue.append(t) # O(1)
        while t - self.queue[0] > 3000: # 최악의 경우는 O(n)이지만, 평균적으로는 O(1)
            self.queue.popleft() # O(1)
        return len(self.queue) # O(1)

 

while t - self.queue[0] > 3000

최악의 경우, deque에 있는 모든 요소를 확인할 수 있다. 그러나 실제로 각 요소는 한 번만 deque에 들어가고 한 번만 나오기 때문에, 이 연산의 평균 시간 복잡도는 O(1)로 간주할 수 있다.

 

요청시간 동안 들어온 요청을 보관하기 위한 deque을 생성하므로, 공간 복잡도는 O(n)이다.