O(n³) 중첩 루프를 Sliding Window로 변경하여 O(n) 시간 복잡도 달성

Pattern Recognition: The Secret Weapon Top Coders Actually Use

Timevolt2026년 6월 5일6분intermediate

AI 요약

Context

특정 가맹점에서 5분 내 3회 이상 구매한 사용자를 탐지하는 Fraud Detection 로직 구현 과정. 기존 설계는 3중 중첩 루프를 사용하여 데이터 증가 시 처리 시간이 기하급수적으로 늘어나는 O(n³) 시간 복잡도의 병목 지점 발생.

시간 순 정렬된 데이터를 전제로 Sliding Window 패턴을 적용한 단일 패스 처리 구조 설계
Hash Map 기반의 merchantQueue를 구축하여 각 가맹점별 타임스탬프 큐를 개별 관리
신규 이벤트 유입 시 큐에 추가하고 windowMs(300,000ms)를 초과한 오래된 데이터를 shift()로 제거하는 Pruning 로직 구현
큐의 길이를 체크하여 3개 이상의 이벤트 존재 시 즉시 플래그를 지정하는 단순화된 검증 프로세스 채택
데이터 무결성 확보를 위해 전처리 단계에서 타임스탬프 기준 정렬(Sort) 수행
불필요한 반복 연산을 제거하여 각 요소가 큐에 한 번 진입하고 한 번 퇴출되는 선형 구조 완성

실천 포인트

1. 시간 범위 내 빈도수 측정 필요 시 Sliding Window 적용 검토

2. Hash Map을 활용해 상태(State)를 그룹화하여 조회 시간 O(1) 유지

3. 윈도우 기반 로직 적용 전 입력 데이터의 정렬 상태 확인

4. 중첩 루프 발생 시 이를 선형 시간 복잡도로 대체할 수 있는 자료구조 탐색

태그