[LeetCode - 238] Products of Array Discluding Self - C++

문제

Products of Array Discluding Self

Given an integer array nums, return an array output where `output[i]` is the product of all the elements of nums except `nums[i]`.

Each product is guaranteed to fit in a 32-bit integer.

Follow-up: Could you solve it in 𝑂(𝑛) time without using the division operation?

Example 1:

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

Example 2:

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

Constraints:

`2 <= nums.length <= 1000`
`-20 <= nums[i] <= 20`

 

풀이

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 1);

        for(int i=1; i<n; i++)
            ans[i] = ans[i-1] * nums[i-1];

        int acc = 1;
        for(int i=n-2; i>=0; i--) {
            acc *= nums[i+1];
            ans[i] *= acc;
        }

        return ans;
    }
};

나눗셈을 사용하지 않고 선형시간에 풀라는 제약조건이 없다면 아주 쉬운 문제다.

우선 `nums`의 원소를 모두 곱한 후 `ans[i] = prod / nums[i]`로 답을 선형 시간에 구할 수 있다.

 

나누기를 사용하지 말라는 조건이 신선했다. 

 

기본 아이디어는 `ans[k] = nums[0] * nums[1] * ... * nums[k-1] * nums[k+1] * ... * nums[n-1]`이므로 

rightward로 누적곱과 leftward로 누적곱을 계산해 `k`의 양쪽의 누적곱을 곱해 `ans[k]`를 계산하는 아이디어다.

 

처음에는 두개의 누적곱을 계산하는 배열을 만들어 구현했다.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        int leftward[n], rightward[n];
        rightward[0] = nums[0];
        leftward[n-1] = nums[n-1];

        for(int i=1; i<n; i++) {
            rightward[i] = rightward[i-1] * nums[i];
            leftward[n-1-i] = leftward[n-i] * nums[n-1-i];
        }

        vector<int> ans(n, 1);
        for(int i=0; i<n; i++) {
            if(i > 0) ans[i] *= rightward[i - 1];
            if(i < n-1) ans[i] *= leftward[i + 1];
        }
        return ans;
    }
};

선형 누적 계산이어서 추가적인 저장공간을 사용하지 않고 풀 수 있을 것 같다는 생각에 더 고민해봤고 `ans`만을 이용한 풀이를 생각했다.