JavaScript 슬라이딩 윈도우로 곱이 target보다 작은 연속 부분 배열 개수 세기

문제 소개

숫자 배열 arr와 숫자 target을 인자로 받는 JavaScript 함수를 작성해야 합니다. 함수는 모든 요소의 곱이 target보다 작은 연속(contiguous) 부분 배열의 개수를 세어 반환해야 합니다.

예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

입력

const arr = [10, 5, 2, 6];
const target = 100;

출력

const output = 8;

출력 설명

곱이 100보다 작은 부분 배열은 총 8개입니다.

[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]

주의할 점은 [10, 5, 2]는 포함되지 않는다는 것입니다. 이 배열의 곱이 정확히 100으로, target보다 엄격하게 작지 않기 때문입니다.

접근 방법: 슬라이딩 윈도우

모든 부분 배열을 일일이 확인하는 브루트포스 방식은 O(n²) 이상의 시간이 걸릴 수 있습니다. 반면 슬라이딩 윈도우(sliding window) 기법을 사용하면 O(n) 시간 복잡도로 문제를 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

1. product 변수가 현재 윈도우 내 요소들의 곱을 유지합니다.
2. right 포인터가 오른쪽으로 확장될 때마다 해당 요소를 product에 곱합니다.
3. product가 target 이상이 되면, 조건을 만족할 때까지 왼쪽 끝 요소를 나누고 left를 이동시켜 윈도우를 축소합니다.
4. 윈도우가 유효해지면, right를 오른쪽 끝으로 가지는 유효한 부분 배열의 개수(right - left + 1)를 count에 더합니다.

코드 구현

위 접근 방식을 코드로 구현하면 다음과 같습니다.

const arr = [10, 5, 2, 6];
const target = 100;
const countSubarrays = (arr = [], target = 1) => {
    let product = 1
    let left = 0
    let count = 0
    for (let right = 0; right < arr.length; right++) {
        product *= arr[right]
        while (left <= right && product >= target) {
            product /= arr[left]
            left += 1
        }
        count += right - left + 1
    }
    return count
};
console.log(countSubarrays(arr, target));

실행 결과

8

복잡도 분석

각 요소는 최대 한 번 추가되고 한 번 제거되므로 시간 복잡도는 O(n)이며, 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 배열에 양수만 포함되어 있다면 곱이 확장 시 증가하고 축소 시 감소한다는 성질 덕분에 이 기법이 안정적으로 동작합니다.