C++로 히트 카운터 설계하기: 지난 5분간의 히트 수 집계 알고리즘

문제 소개

지난 5분 동안 받은 히트(hit) 수를 집계하는 히트 카운터(Hit Counter)를 설계한다고 가정해 보겠습니다. 이 카운터는 초 단위의 타임스탬프(timestamp)를 매개변수로 받는 함수를 제공하며, 호출은 항상 시간 순서대로 이루어진다고 가정합니다. 즉, 타임스탬프는 단조롭게 증가하고, 가장 이른 타임스탬프는 1부터 시작합니다.

또한 여러 개의 히트가 거의 같은 시점에 몰려서 도착할 수도 있습니다.

구현해야 할 함수는 다음 두 가지입니다.

hit(timestamp): 해당 시점에 히트가 발생했음을 기록합니다.
getHits(timestamp): 현재 시점을 기준으로 지난 5분간의 총 히트 수를 반환합니다.

접근 방법

5분은 정확히 300초입니다. 따라서 크기가 300인 두 개의 배열을 준비하면 링 버퍼(ring buffer)처럼 활용할 수 있습니다.

time[300]: 각 슬롯에 마지막으로 히트가 기록된 타임스탬프를 저장합니다.
hits[300]: 각 슬롯에 해당 초 동안 발생한 히트 수를 저장합니다.

타임스탬프를 300으로 나눈 나머지(modulo)를 인덱스로 사용하면, 아무리 큰 값이 들어와도 항상 0~299 범위의 슬롯에 매핑됩니다. 새로운 타임스탬프가 해당 슬롯에 저장된 기존 값과 다르면 슬롯을 초기화하고, 같으면 카운트만 1 증가시킵니다.

알고리즘 단계

크기 300의 배열 time과 hits를 선언합니다.
hit(timestamp) 함수:
- idx = timestamp % 300으로 인덱스를 계산합니다.
- time[idx]가 현재 타임스탬프와 다르면 time[idx] = timestamp, hits[idx] = 1로 설정합니다.
- 같다면 hits[idx]를 1 증가시킵니다.
getHits(timestamp) 함수:
- 결괏값 ret = 0으로 초기화합니다.
- i가 0부터 299까지 반복하면서 timestamp - time[i] < 300이면 ret += hits[i]를 수행합니다.
- ret을 반환합니다.

C++ 구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class HitCounter {
public:
    vector<int> time;
    vector<int> hits;
    HitCounter(){
        time = vector<int>(300);
        hits = vector<int>(300);
    }
    void hit(int timestamp){
        int idx = timestamp % 300;
        if (time[idx] != timestamp) {
            time[idx] = timestamp;
            hits[idx] = 1;
        }
        else {
            hits[idx] += 1;
        }
    }
    int getHits(int timestamp){
        int ret = 0;
        for (int i = 0; i < 300; i++) {
            if (timestamp - time[i] < 300) {
                ret += hits[i];
            }
        }
        return ret;
    }
};
main(){
    HitCounter ob;
    ob.hit(1);
    ob.hit(2);
    ob.hit(3);
    cout << (ob.getHits(4)) << endl;
    ob.hit(300);
    cout << (ob.getHits(300)) << endl;
    cout << (ob.getHits(301));
}

입력

ob.hit(1);
ob.hit(2);
ob.hit(3);
ob.getHits(4);
ob.hit(300);
ob.getHits(300);
ob.getHits(301);

출력

3
4
3

결과 해석

getHits(4) → 3: 타임스탬프 1, 2, 3에서 발생한 히트가 모두 최근 5분 이내이므로 3을 반환합니다.
getHits(300) → 4: 타임스탬프 300에 히트가 추가되어 총 4개가 됩니다.
getHits(301) → 3: 301 − 1 = 300이므로 타임스탬프 1의 히트는 5분 범위를 벗어나 제외됩니다.

복잡도 분석

시간 복잡도: hit()은 O(1)이며, getHits()는 최대 300개의 슬롯만 확인하므로 사실상 O(1)입니다.
공간 복잡도: 고정 크기 배열 두 개만 사용하므로 O(300), 즉 상수 공간 O(1)입니다.