만료 시간(expire time)을 가지며, 사용자 ID와 타임스탬프를 인자로 받아 해당 시점의 요청이 실패하는지 여부를 판단하는 함수를 지원하는 데이터 구조를 개발한다고 가정해 봅시다. 요청은 오직 해당 사용자가 만료 시간 이내에 성공적인 요청을 보낸 기록이 있을 때만 실패하게 됩니다.
동작 예시
예를 들어 expire = 6으로 객체 obj를 생성한 뒤, 다음 순서대로 함수를 호출한다고 해봅시다.
obj.limit(0, 10)→ False: 사용자 0의 첫 요청이므로 기록이 없어 통과됩니다.obj.limit(0, 16)→ False: 마지막 요청 시각 10에 만료 시간 6을 더한 값(16)이 현재 시각 16보다 작거나 같으므로 통과됩니다.obj.limit(0, 17)→ True: 직전 요청이 시각 16에 있었고, 16 + 6 = 22가 17보다 크므로 만료 시간 이내라 요청이 거부됩니다.obj.limit(1, 20)→ False: 사용자 1에 대한 첫 요청이므로 통과됩니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 생성자(
__init__)를 정의하고, 만료 시간expire를 저장합니다. - 기본값이 -1인 딕셔너리
lastCall을 생성하여 각 사용자의 마지막 요청 시각을 추적합니다. - 함수
limit(uid, timestamp)를 정의합니다. last에lastCall[uid]값을 저장합니다.last가 -1이거나(last + expire) <= timestamp라면:lastCall[uid]를 현재 타임스탬프로 갱신합니다.False(요청 허용)를 반환합니다.
- 그렇지 않으면
True(요청 거부)를 반환합니다.
구현 코드
다음 구현을 통해 더 잘 이해해 보겠습니다.
from collections import defaultdict
class RateLimit:
def __init__(self, expire):
self.expire = expire
self.lastCall = defaultdict(lambda: -1)
def limit(self, uid, timestamp):
last = self.lastCall[uid]
if last == -1 or last + self.expire <= timestamp:
self.lastCall[uid] = timestamp
return False
return True
expire = 6
obj = RateLimit(expire)
print(obj.limit(0,10))
print(obj.limit(0,16))
print(obj.limit(0,17))
print(obj.limit(1,20))입력
RateLimit(6) obj.limit(0,10) obj.limit(0,16) obj.limit(0,17) obj.limit(1,20)
출력
False False True False
코드 설명
핵심 아이디어는 collections.defaultdict를 활용해 각 사용자의 마지막 성공 요청 시각을 저장하는 것입니다. 새로운 사용자가 조회되면 자동으로 -1이 할당되므로 별도의 초기화 처리 없이 "첫 요청 여부"를 쉽게 판별할 수 있습니다. limit() 함수는 마지막 요청 시각에 만료 시간을 더한 값이 현재 타임스탬프보다 작거나 같은 경우에만 요청을 허용하고, 그렇지 않으면 요청을 거부합니다. 이 구조의 시간 복잡도는 호출당 O(1)이며, 공간 복잡도는 고유 사용자 수에 비례해 O(U)입니다.