자바스크립트 코딩테스트 강좌, 구간 곱 구하기

코딩 인터뷰에서 종종 주어지는 문제 중 하나가 배열의 특정 구간(서브배열)의 곱을 구하는 문제입니다. 본 강좌에서는 이를 구간 곱 구하기 문제로 정의하고, 이를 해결하는 방법을 자세히 설명하겠습니다.

문제 정의

배열 A와 쿼리 리스트가 주어질 때, 각 쿼리는 구간 [L, R]을 포함하며, 우리는 A[L]에서 A[R]까지의 곱을 계산해야 합니다. 주어진 배열 A와 쿼리가 다음과 같다고 가정합시다:

A = [2, 3, 4, 5, 6]
쿼리 = [(1, 3), (0, 2), (2, 4)] // 인덱스는 0부터 시작

각 쿼리의 결과를 출력해야 합니다. 예를 들어, 쿼리 (1, 3)의 경우, A[1] * A[2] * A[3] = 3 * 4 * 5 = 60이 됩니다.

문제 이해

이 문제를 해결하기 위해서는 몇 가지 문제의 조건을 이해해야 합니다:

배열 A의 크기와 각 쿼리의 구간 (L, R)의 유효성 검증
구간의 곱을 빠르게 구하는 방법
배열의 각 요소가 주어질 때, 여러 번의 곱을 계산하는 비효율성 문제를 어떻게 해결할 것인가

해결 전략

구간 곱을 효율적으로 계산하기 위해 프리픽스 곱 (prefix product)를 활용할 수 있습니다. 이 방법은 초기 배열 A로부터 새로운 배열 P(A)를 생성하여 각 인덱스 i에 대해 A의 0번 인덱스부터 i번 인덱스까지의 곱을 저장합니다. 그러면 쿼리 (L, R)의 곱은 다음과 같이 계산할 수 있습니다.

구간 곱 Q(L, R) = P(R) / P(L - 1)

여기서 P(i)는 인덱스 i까지의 곱을 의미하며, P(0)은 A[0]입니다.

구현

이제 위의 전략을 바탕으로 자바스크립트 코드를 구현해 보겠습니다:


function productRange(arr, queries) {
    // 배열의 크기
    const n = arr.length;

    // 프리픽스 곱 배열을 초기화
    const prefixProduct = new Array(n);
    prefixProduct[0] = arr[0];

    // 프리픽스 곱을 계산
    for (let i = 1; i < n; i++) {
        prefixProduct[i] = prefixProduct[i - 1] * arr[i];
    }

    // 결과 배열 초기화
    const result = [];

    // 쿼리 처리
    queries.forEach(([L, R]) => {
        if (L === 0) {
            result.push(prefixProduct[R]);
        } else {
            result.push(prefixProduct[R] / prefixProduct[L - 1]);
        }
    });

    return result;
}

// 테스트
const A = [2, 3, 4, 5, 6];
const queries = [[1, 3], [0, 2], [2, 4]];
console.log(productRange(A, queries)); // 결과 기대: [60, 24, 120]

분석

위 코드의 시간 복잡도는 O(N + Q)입니다. 여기서 N은 배열의 크기, Q는 쿼리의 수입니다. 프리픽스 곱을 계산하는 데 O(N)의 시간이 소요되고, 각 쿼리를 처리하는 데 O(1)의 시간이 소요되기 때문입니다.

이 방식은 구간 곱 문제를 효율적으로 해결할 수 있게 해 주며, 다양한 조건에서의 쿼리 처리에도 유용합니다.

대안적 방법

만약 배열에 변경이 가해질 경우, 업데이트하거나 동적으로 길어지는 쿼리에 대한 효율적인 데이터 구조가 필요할 수 있습니다. 이 경우 세그먼트 트리와 같은 자료 구조를 활용할 수 있습니다. 이를 통해 업데이트와 쿼리 처리 모두 O(log N) 시간 내에 할 수 있습니다.

결론

이번 강좌에서는 자바스크립트로 구간 곱을 계산하는 문제를 다루어 보았습니다. 배열의 프리픽스 곱을 활용하여 효율적으로 문제를 해결할 수 있음을 보여주었고, 필요할 경우 더 복잡한 구조로 확장할 수 있음을 언급했습니다.

여러분도 이러한 기법을 활용하여 자신만의 코딩 문제를 해결해 보세요!

문제 정의

문제 이해

해결 전략

구현

분석

대안적 방법

결론

관련