[LeetCode] 238. Product of Array Except Self, Medium

1. 문제

• 정수 배열 nums가 주어질 때, answer[i]에 자기 자신을 제외한 요소의 곱을 저장한 배열을 반환하라.

2. 해결

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;

    const ans = new Array(n).fill(1);

    let left = 1;

    for(let i =0; i< n; i++) {
        ans[i] = left;
        left *= nums[i];
    }


    let right = 1;
    for(let i = n -1; i>=0; i--) {
        ans[i] *= right;
        right *= nums[i];
    }
        
    return ans
}

• 못풀었다.
• prefix Sum이라는 기법을 사용하는 거 같은데, ans를 배열로 선언하고, 왼쪽 -> 오른쪽으로 향하면서 i번 째 정답 배열에 i-1까지의 곱을 누적해두고, 오른쪽 -> 왼쪽으로 향하면서 i 번 째 정답 배열에 i+1까지의 곱을 누적해둔다.
• i 번 째 정답 배열에는 i-1 까지의 곱  * i+1까지의 곱을 담으면 자기 자신을 제외한 요소의 곱이 담긴다.