99클럽 코테 스터디 26일차 TIL

 

오늘의 공부 키워드

933 Number of Recent Calls

 

933 Number of Recent Calls

 

문제 설명

RecentCounter 클래스는 특정 시간 프레임 내에서 최근 요청의 수를 카운트하는 클래스입니다. 이 클래스를 구현하세요:

• RecentCounter(): 초기화 시, 최근 요청의 수를 0으로 설정합니다.
• int ping(int t): 시간 t에서 새로운 요청을 추가합니다. 여기서 t는 밀리초 단위의 시간을 나타내며, 지난 3000 밀리초 동안(새로운 요청을 포함하여) 발생한 요청의 수를 반환합니다. 구체적으로, [t - 3000, t] 범위에 해당하는 요청의 수를 반환합니다.

각 ping 호출은 이전 호출보다 엄격히 더 큰 값을 사용합니다.

 

예제 1:

입력:

["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]

 

출력:

[null, 1, 2, 3, 3]

 

설명:

RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // 요청 = [1], 범위는 [-2999, 1], 반환 값은 1
recentCounter.ping(100);   // 요청 = [1, 100], 범위는 [-2900, 100], 반환 값은 2
recentCounter.ping(3001);  // 요청 = [1, 100, 3001], 범위는 [1, 3001], 반환 값은 3
recentCounter.ping(3002);  // 요청 = [1, 100, 3001, 3002], 범위는 [2, 3002], 반환 값은 3

 

제약 사항:

• 1 <= t <= 10^9
• 각 테스트 케이스는 ping을 호출할 때 엄격히 증가하는 값을 사용합니다.
• 최대 10^4번 ping을 호출할 수 있습니다.

파이썬코드

from collections import deque

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

    def ping(self, t: int) -> int:
        self.queue.append(t)
        # Remove elements that are out of the 3000ms range
        while self.queue[0] < t - 3000:
            self.queue.popleft()
        return len(self.queue)

# Example usage
recentCounter = RecentCounter()
print(recentCounter.ping(1))     # Output: 1
print(recentCounter.ping(100))   # Output: 2
print(recentCounter.ping(3001))  # Output: 3
print(recentCounter.ping(3002))  # Output: 3

 

풀이 방법

이 문제를 해결하기 위해서 RecentCounter 클래스를 큐를 사용하여 구현할 수 있습니다. 큐를 사용하면 가장 오래된 요청을 효율적으로 제거하면서 새로운 요청을 추가할 수 있습니다. 다음은 구체적인 풀이 단계입니다:

1. 초기화:
   • __init__ 메서드에서 큐를 초기화합니다.
2. ping 메서드:
   • 새로운 요청이 들어오면 큐에 추가합니다.
   • 큐에서 t - 3000보다 작은 모든 요청을 제거합니다.
   • 큐의 크기를 반환합니다.

이 클래스는 ping 메서드가 호출될 때마다 큐를 업데이트하고, 큐의 크기를 반환함으로써 지난 3000 밀리초 동안의 요청 수를 계산합니다. deque를 사용하여 큐의 앞과 뒤에서 효율적으로 요소를 추가하고 제거할 수 있습니다.