Monotonicity 기반 Subtraction 패턴을 통한 구간 쿼리 복잡도 최적화

Why I Stopped Trying to Count "Exactly Right" and Started Subtracting

Avinash Tyagi2026년 4월 26일6분intermediate

AI 요약

Context

Subarray의 Maximum 값이 특정 범위 [left, right] 내에 존재하는 개수를 산출하는 문제에서 3가지 상태(Too small, In-range, Too big)를 동시에 처리하는 Sliding Window 로직의 복잡성 발생. 조건부 분기 증가로 인한 코드 가독성 저하 및 런타임 오류 가능성 증대.

Technical Solution

범위 제약 조건을 'Exact'에서 'At Most' 형태의 단방향 제약으로 변환하여 문제 단순화
count_at_most(k) 함수를 설계하여 Maximum ≤ k를 만족하는 모든 Subarray 개수를 선형 시간 복잡도로 산출
특정 위치 i에서 끝나는 유효 Subarray의 개수가 현재 Window length와 동일하다는 수학적 특성 활용
'Exactly [left, right]' 문제를 'atMost(right) - atMost(left - 1)'라는 차분 연산으로 재정의하여 복잡한 분기 제거
Window 내 요소 제거 시에도 속성이 유지되는 Monotonicity 원리를 적용하여 Sliding Window 최적화
단일 경계 조건 처리 방식을 통해 다중 포인터 관리 비용 절감 및 로직 일관성 확보

실천 포인트

1. 구간 제약 조건이 포함된 문제에서 if/else 분기가 과도하게 증가하는지 검토

2. 대상 문제의 속성이 Monotonicity(부분 집합이 원래 집합의 속성을 유지함)를 가지는지 확인

3. 'Exactly K' 문제를 'At Most K'와 'At Most K-1'의 차이로 변환 가능한지 분석

4. Window Size를 활용한 누적 합산 방식으로 시간 복잡도를 O(N)으로 최적화할 수 있는지 검토

태그

#Monotonicity #Subarray #Sliding Window #Algorithm Optimization #Time Complexity

원문 읽기