LeetCode 238 - Product of Array Except Self (Medium)

 

💡 문제

LeetCode - 238번

 

🎯 풀이 과정

배열 num 에서 i 번째 요소만 제외한 나머지 요소들의 곱을 i 번째 인덱스에 할당한 결과를 반환해야합니다.

이때 O(n) 의 시간복잡도로 수행되어야하고, 나누기 연산을 사용하면 안되는 제약조건이 있습니다.

이를 위해서 i 번째 요소를 제외한 나머지 요소들의 곱을 다음과 같이 나눠서 생각할 수 있습니다.

 

answer[i] = num[0...i-1] * num[i+1...]

 

부분합 알고리즘을 차용하면, 위에서 필요한 구간곱을 미리 계산해놓을 수 있습니다.

한 배열에는 왼쪽에서부터 누적한 곱을 저장하고, 다른 배열에는 오른쪽에서부터 누적한 곱을 저장합니다.

그러면 위 식은 다음과 같이 바꿔서 계산할 수 있습니다.

 

answer[i] = prefixLeft[i-1] * prefixRight[i+1]

 

👨‍💻 코드

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const leftPrefix = Array(nums.length).fill(0)
    leftPrefix[0] = nums[0]
    for (let idx = 1; idx < nums.length; idx += 1) {
        leftPrefix[idx] = leftPrefix[idx-1] * nums[idx]
    }

    const rightPrefix = Array(nums.length).fill(0) 
    rightPrefix[nums.length-1] = nums[nums.length-1]
    for (let idx = nums.length-2; idx >= 0; idx -= 1) {
        rightPrefix[idx] = rightPrefix[idx+1] * nums[idx]
    }

    const answer = Array(nums.length).fill(0)
    for (let idx = 0; idx < nums.length; idx += 1) {
        answer[idx] = (leftPrefix[idx-1] ?? 1) * (rightPrefix[idx+1] ?? 1)
    }

    return answer
};