[Leetcode] 238. Product of Array Except Self (Medium) - javascript

📝 문제

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

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

 

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

 

🤔 나의 풀이

1. 시간복잡도 생각하지 않은 풀이 => 실패

var productExceptSelf = function(nums) {
    let answer = [];
    for(let i = 0; i < nums.length; i++) {
        let array = nums.filter((v,idx) => idx !== i);
        answer.push(array.reduce((ac,v) => ac * v, 1));
    }
    return answer;
};

 

2. O(n)의 풀이 => 성공

var productExceptSelf = function(nums) {
    let answer = [];
    let zeroCnt = nums.filter(v => v === 0).length;
    let sum;
    
    // 0이 없을때
    if(zeroCnt === 0) {
        sum = nums.reduce((ac,v) => ac * v, 1);
        for(let i = 0; i < nums.length; i++) {
            answer.push(sum/nums[i]);
        }
    }
    
    // 0이 하나일때
    else if(zeroCnt === 1) {
        sum = nums.reduce((ac,v) => v !== 0 ? ac * v : ac, 1);
        for(let i = 0; i < nums.length; i++) {
            answer.push(nums[i] === 0 ? sum : 0);
        }
    }
    
    // 0이 여러개일때
    else {
        answer = Array(nums.length).fill(0);
    }
    
    return answer;
};

 

-30 <= nums[i] <= 30 라는 조건에서 힌트를 얻어서 해결했다.

보통 이런 문제는 요소가 정수일 것이라 생각하기 쉽지만 음수, 0도 포함되어 있는지 파악해야 한다.

오랜만에 막 짜지 않고 시간복잡도를 생각해서 만든 코드!