Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 요청 속도 제한 조건에 따라 처리되는 요청 수 계산하기

문제 설명

웹사이트로 들어오는 요청 목록이 주어졌다고 가정해 보겠습니다. 각 요청은 [uid, time_sec] 형태로 표현되며, uid는 사용자 ID, time_sec는 요청이 발생한 타임스탬프(초 단위)를 의미합니다. 즉, 해당 사용자가 time_sec 시점에 웹사이트에 요청을 보냈다는 뜻입니다.

여기에 두 개의 제한 값이 추가로 주어집니다.

  • u: 특정 사용자(uid)가 60초 미만의 시간 창(window) 내에서 허용되는 최대 요청 수
  • g: 전체 시스템 기준으로 60초 미만의 시간 창 내에서 허용되는 최대 요청 수

각 요청을 순서대로 처리하면서 위 조건에 따라 속도 제한(rate limit)을 적용해야 합니다. 여러 사용자가 동시에 요청을 보내는 경우에는 uid가 더 작은 사용자의 요청을 먼저 처리하며, 제한 조건을 만족하지 못하는 요청은 폐기(drop)됩니다. 최종적으로 구해야 하는 값은 성공적으로 처리된 요청의 총 개수입니다.

예시

입력이 다음과 같다고 해보겠습니다.

  • requests = [[0, 1], [1, 2], [1, 3]]
  • u = 1, g = 5

이때 출력은 2입니다. 사용자 0과 1은 각각 시각 1과 2에 요청을 보낼 수 있지만, 사용자 1의 두 번째 요청(시각 3)은 한 사용자가 60초 창 안에서 최대 1개의 요청만 보낼 수 있다는 제한(u = 1) 때문에 처리되지 않습니다.

해결 접근 방법

이 문제는 슬라이딩 윈도우(sliding window) 방식으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.

  1. last: 사용자별 요청 시각을 저장하는 빈 맵(defaultdict)을 생성합니다.
  2. total: 전체 요청 시각을 저장하는 빈 데크(deque)를 생성합니다.
  3. windowtime := 60으로 설정합니다.
  4. 요청 목록을 시간 기준으로 오름차순 정렬하고, 시간이 같으면 uid 기준으로 정렬합니다.
  5. amount := 0으로 초기화합니다.
  6. requests의 각 요청 r에 대해 다음을 반복합니다.
    • [uid, time] := r로 분해합니다.
    • total이 비어 있지 않고 total[0] + windowtime <= time인 동안, total의 왼쪽 항목을 삭제합니다. (윈도우 밖의 오래된 요청 제거)
    • last[uid]가 비어 있지 않고 last[uid][0] + windowtime <= time인 동안, last[uid]의 왼쪽 항목을 삭제합니다.
    • len(total) < g 이고 len(last[uid]) < u 라면:
      • last[uid]의 끝에 time을 삽입합니다.
      • total의 끝에 time을 삽입합니다.
      • amount를 1 증가시킵니다.
  7. amount를 반환합니다.

파이썬 구현 코드

다음 코드를 통해 실제 동작을 확인해 보겠습니다.

from collections import defaultdict, deque
class Solution:
   def solve(self, requests, u, g):
      last = defaultdict(deque)
      total = deque()

      windowtime = 60
      requests.sort(key=lambda x: [x[1], x[0]])

      amount = 0
      for r in requests:
         uid, time = r

         while len(total) > 0 and total[0] + windowtime <= time:
            total.popleft()

         while len(last[uid]) > 0 and last[uid][0] + windowtime <= time:
            last[uid].popleft()

         if len(total) < g and len(last[uid]) < u:
            last[uid].append(time)
            total.append(time)
            amount += 1
      return amount
     
ob = Solution()
requests = [[0, 1],[1, 2],[1,3]]
u = 1
g = 5
print(ob.solve(requests, u, g))

입력

[[0, 1],[1, 2],[1,3]], 1, 5

출력

2

동작 원리 정리

이 알고리즘의 핵심은 두 개의 데크를 활용하는 것입니다. total 데크는 전역 요청 제한(g)을 검증하는 데 사용되고, last[uid] 데크는 사용자별 요청 제한(u)을 검증하는 데 사용됩니다. 새 요청이 들어올 때마다 60초 윈도우를 벗어난 오래된 기록들을 먼저 제거한 뒤, 현재 윈도우 내의 요청 수가 두 제한 조건을 모두 만족하는 경우에만 요청을 승인하고 기록에 추가합니다. 이 방식의 시간 복잡도는 정렬에 O(n log n), 요청 처리에 O(n)이므로 전체적으로 O(n log n)입니다.