[Leet Code Top 100] #238. Product of Array Except Self

문제 정보

• Leet Code 문제 링크
• 난이도 : Medium

 

해결 방법

문제의 답 자체는 모든 수를 for loop 나 reduce 메소드를 가지고 모든 수의 곱을 nums[i] divide 하고 0 으로 나누는 경우는 나머지를 모두 곱해서 구할 수 있습니다. 하지만 아래와 같이 제한 사항이 있기 때문에 for loop 를 순회하면서 나눗셈을 사용하지 않아야 합니다.

You must write an algorithm that runs in O(n) time and without using the division operation.

loop 를 두 번 순회하면서 왼쪽과 오른쪽으로 나누어 곱한 값을 result Array 에 저장하고 나머지 값을 곱해서 반환합니다.

 

소스 코드

// Leet Code
// #238. Product of Array Except Self
// Success
// Runtime: 226 ms, faster than 13.29% of JavaScript online submissions for Product of Array Except Self.
// Memory Usage: 52.4 MB, less than 22.97% of JavaScript online submissions for Product of Array Except Self.

function main(){
    // Input
    nums = [1,2,3,4];
    // Output
    // [24,12,8,6]
    console.log(productExceptSelf(nums));
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
// var productExceptSelf = function(nums) {
//     const result = [];
//     let nums_except_i = [];
    
//     for(let idx = 0; idx < nums.length; idx++){
//         nums_except_i = nums.slice(0, idx).concat(nums.slice(idx + 1));
//         result.push(nums_except_i.reduce((acc, elem) => acc * elem, 1));
//     }

//     return result;
// };

var productExceptSelf = function(nums) {
    const result = [];
    
    let leftMul = 1;
    let rightMul = 1;

    for(let leftIdx = 0; leftIdx < nums.length; leftIdx++){
        result[leftIdx] = leftMul;
        leftMul *= nums[leftIdx];
        //console.log(`leftIdx:${leftIdx} / result:${result[leftIdx]}`);
    }

    for(let rightIdx = nums.length - 1; 0 <= rightIdx; rightIdx--){
        result[rightIdx] = result[rightIdx] * rightMul;
        rightMul *= nums[rightIdx];
        //console.log(`rightIdx:${rightIdx} / result:${result[rightIdx]}`);
    }

    return result;
};

main();

 

참고 자료

• LeetCode Top 100 Problem Selection