파이썬으로 최근 호출 수 세기: 큐를 활용한 RecentCounter 클래스 구현

문제 개요

최근 요청의 개수를 세는 RecentCounter 클래스를 작성한다고 가정해 보겠습니다. 이 클래스에는 ping(t)라는 단 하나의 메서드가 있으며, 매개변수 t는 밀리초(ms) 단위의 시간을 나타냅니다.

ping(t)를 호출하면 현재 시점부터 3000밀리초 전까지의 범위, 즉 [t - 3000, t] 구간에서 발생한 모든 핑(ping)의 개수를 반환합니다. 당연히 현재 호출된 핑도 개수에 포함됩니다. 또한 ping을 호출할 때마다 t 값은 항상 이전 호출보다 엄격하게 커진다는 것이 보장됩니다.

예를 들어 ping(1), ping(100), ping(3001), ping(3002) 순서로 네 번 호출하면 출력은 각각 1, 2, 3, 3이 됩니다.

해결 접근 방법

이 문제는 큐(Queue) 자료구조를 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 유효 범위를 벗어난 오래된 핑을 계속 제거하고, 남아 있는 핑의 개수만 세는 것입니다. 단계별로 살펴보면 다음과 같습니다.

• 클래스를 초기화할 때 빈 큐(리스트)를 하나 생성합니다.
• ping(t) 함수를 정의합니다.
• 큐가 비어 있지 않고 t - queue[0] > 3000인 동안, 즉 맨 앞의 핑이 유효 범위를 벗어나는 동안 큐의 첫 번째 요소를 삭제합니다.
• 현재 시간 t를 큐의 끝에 추가합니다.
• 큐의 크기, 즉 남아 있는 핑의 개수를 반환합니다.

예제 코드

class RecentCounter:
    def __init__(self):
        self.queue = []

    def ping(self, t):
        while len(self.queue) and t - self.queue[0] > 3000:
            self.queue.pop(0)
        self.queue.append(t)
        return len(self.queue)

ob = RecentCounter()
print(ob.ping(1))
print(ob.ping(100))
print(ob.ping(3001))
print(ob.ping(3002))

입력

ob.ping(1)
ob.ping(100)
ob.ping(3001)
ob.ping(3002)

출력

1
2
3
3

코드 동작 원리

호출 흐름을 하나씩 추적해 보면 다음과 같습니다.

• ping(1): 큐가 비어 있으므로 삭제 없이 1을 추가 → 큐 [1], 결과 1
• ping(100): 100 − 1 = 99 ≤ 3000이므로 기존 핑 유지 → 큐 [1, 100], 결과 2
• ping(3001): 3001 − 1 = 3000으로 경계값 이내이므로 모두 유효 → 큐 [1, 100, 3001], 결과 3
• ping(3002): 3002 − 1 = 3001 > 3000이므로 1을 제거 → 큐 [100, 3001, 3002], 결과 3

효율성 팁

파이썬 리스트의 pop(0)은 첫 번째 요소를 제거할 때 나머지 요소들을 모두 앞으로 당겨야 하므로 O(n)의 시간이 걸립니다. 따라서 실무에서는 collections.deque를 사용하는 것이 좋습니다. deque는 양방향 삽입·삭제가 O(1)로 처리되어 훨씬 효율적입니다.

from collections import deque

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

    def ping(self, t):
        while self.queue and t - self.queue[0] > 3000:
            self.queue.popleft()
        self.queue.append(t)
        return len(self.queue)

이처럼 큐의 선입선출(FIFO) 특성을 활용하면 시간 범위 조건을 만족하는 요청만 효율적으로 관리할 수 있습니다.