O(n²) Brute-force를 O(n) Linear Time으로 최적화한 Sliding Window 패턴 분석

Context

연속된 데이터 부분 집합에서 특정 조건을 만족하는 최적의 구간을 찾는 문제 상황 분석. 중첩 루프를 통한 전수 조사 방식의 O(n²) 시간 복잡도로 인한 대규모 데이터셋 처리 시 Timeout 발생 및 성능 병목 지점 식별.

Technical Solution

• 데이터의 Monotonicity 특성을 활용하여 불필요한 중복 탐색을 제거한 Sliding Window 구조 설계
• Right Pointer를 통한 윈도우 확장으로 조건 충족 시점까지 데이터 셋을 점진적으로 증가
• 조건 충족 후 Left Pointer를 이동시켜 윈도우를 수축함으로써 최소 구간 혹은 최적 조건을 탐색
• 인접 윈도우 간의 Overlap 구간을 재사용하여 매 단계 O(1)의 연산량만 소모하는 증분 업데이트 로직 적용
• 데이터 성격에 따라 단순 합계는 정수형 변수로, 고유성 검증은 Set 또는 Map 구조를 사용하여 상태 관리