DaleStudy | Leetcode Study 2주차 - Product of Array Except Self

Leetcode Study

문제

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 <= 10^5
• -30 <= nums[i] <= 30

 

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

 

풀이

 

이 문제를 보자마자 나누기를 사용하려고 했는데, 문제에 나누기는 사용하지 말라고 작성되어 있었다. 그럼 나누기를 사용하지 않고 O(n) 시간복잡도를 가질 수 있도록 어떻게 구현할 수 있을까? 답이 안나올 때는 먼저 문제의 제약을 확인하지 않고 구현을 해본다. 

function productExceptSelf(nums: number[]): number[] {
    const results = []

    for (let i=0; i<nums.length; i++) {
        let multiple = 1;
        for (let j=0; j<nums.length; j++) {
            if (i !== j) {
                multiple *= nums[j]
            }
        }
        results.push(multiple)
    }

    return results;
};

 

 

이렇게 풀게 되면 당연히 O(n^2)의 시간복잡도를 갖게 되므로 테스트에 통과하지는 못한다. 좀 더 풀어봐야겠다. 

이 부분은 해답을 조금 참고했다. 일단 답안은 아래의 답안으로 통과할 수 있었다.

function productExceptSelf(nums: number[]): number[] {
    const results = []

    let left = 1;
    let right = 1;

    for (let i=0; i<nums.length; i++) {
        results[i] = left;
        left *= nums[i]
    }

    for (let i=nums.length - 1; i >= 0; i--) {
        results[i] *= right;
        right *= nums[i]
    }
    
    return results;
};

 

먼저, 우리가 [1, 2, 3, 4] 배열의 입력이 주어졌다고 가정해보자. 이 부분을 풀어서 생각하면 아래의 식이 나온다. 여기서 각 원소들을 보면 원소 인덱스를 기준으로 오른쪽과 왼쪽을 나눠서 생각하면 된다. 

[(n+1)*(n+2)*(n+3), (n-1)*(n+1)*(n+2), (n-2)*(n-1)*(n+1), (n-3)*(n-2)*(n-1)]

// 0번째 원소
// 왼: X 
// 오: (n+1)*(n+2)*(n+3)

// 1번째 원소
// 왼: (n-1)
// 오: (n+1)*(n+2)

// 2번째 원소
// 왼: (n-2)*(n-1)
// 오: (n+1)

// 3번째 원소
// 왼: (n-3)*(n-2)*(n-1)
// 오: X

그리고, 왼쪽의 곱을 먼저 해주면, [1, 2, 6, 24]가 되는데 이 배열을 가지고 오른쪽 요소들도 곱을 누적시켜주면 이 문제를 풀 수 있다. 

 

Link: https://leetcode.com/problems/product-of-array-except-self/description/