[leetcode]Product of Array Except Self

Product of Array Except Self

문제

• nums라는 정수 배열이 주어진다.
• answer[i]는 nums[i]를 제외한 모든 요소의 곱이 되어야 한다.
• 단, 나눗셈은 사용할 수 없다.
• 모든 곱은 32비트 정수 범위 내에서 계산된다.

잘못된 접근

// 이렇게 풀면 0이 있는 경우 제대로 동작하지 않는다.
function productExceptSelf(nums) {
    const n = nums.length;
    const res = nums.reduce((a, b) => a * b, 1);
    return nums.map(num => res / num);
}

• 문제점:

  • 배열에 0이 포함될 경우, 나눗셈 방식으로는 올바른 답을 얻을 수 없다.

올바른 접근법 (누적 곱 방식)

핵심 아이디어

• 왼쪽 곱(L): nums[i]의 왼쪽에 있는 모든 수의 곱
• 오른쪽 곱(R): nums[i]의 오른쪽에 있는 모든 수의 곱
• 정답: answer[i] = L[i] * R[i]

구현 순서

1. 왼쪽 누적 곱 계산

   • 왼쪽에서부터 차례대로 곱을 누적하여, 각 위치에 왼쪽 곱 저장

2. 오른쪽 누적 곱 계산

   • 오른쪽에서부터 역순으로 곱을 누적하며, 각 위치에 오른쪽 곱을 곱해줌

3. 최종적으로 answer[i]에는 nums[i]를 제외한 모든 값의 곱이 저장됨

코드: 배열 2개 버전

function productExceptSelf(nums) {
    const n = nums.length;
    const left = Array(n).fill(1);
    const right = Array(n).fill(1);

    // 왼쪽 누적곱
    for (let i = 1; i < n; i++) {
        left[i] = left[i - 1] * nums[i - 1];
    }

    // 오른쪽 누적곱
    for (let i = n - 2; i >= 0; i--) {
        right[i] = right[i + 1] * nums[i + 1];
    }

    // 최종 곱
    const answer = [];
    for (let i = 0; i < n; i++) {
        answer[i] = left[i] * right[i];
    }
    return answer;
}

코드: 공간 최적화 버전

실제로는 배열 두 개를 따로 쓸 필요 없이, 정답 배열 하나만 써서 왼쪽, 오른쪽을 차례로 누적할 수 있다.

function productExceptSelf(nums) {
    const n = nums.length;
    const answer = Array(n).fill(1);

    // 1. 왼쪽 곱 누적
    let left = 1;
    for (let i = 0; i < n; i++) {
        answer[i] = left;
        left *= nums[i];
    }

    // 2. 오른쪽 곱 누적 및 곱셈
    let right = 1;
    for (let i = n - 1; i >= 0; i--) {
        answer[i] *= right;
        right *= nums[i];
    }
    return answer;
}

요약

• 나눗셈 없이 각 원소를 제외한 곱을 구하는 가장 효율적인 방법.
• 왼쪽부터 오른쪽, 오른쪽부터 왼쪽으로 두 번 순회하여 누적곱을 계산.
• 추가 배열 없이도 정답 배열 하나로 해결 가능 (공간복잡도 O(1) 추가 사용).

의문

사실 이 방식이 직관적이지 않게 느껴질 수 있지만,
원리를 이해하려면 각 위치의 왼쪽/오른쪽 곱을 하나씩 누적해서
“자기 자신만 제외한 모든 곱”이란 게 어떻게 만들어지는지 예시를 통해 생각해보면 이해가 쉬움.
또한 예시 요소를 그대로 사용하기 보단, index를 요소에 대입해보면서 시각화를 하는 것이 점화식을 얻기 쉽다.