[PS] Leet | 238. 자신을 제외한 곱

문제

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]

조건

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

답

해당 인덱스를 기준으로 양 옆으로 숫자들을 구분해서 prefix products와 suffix products를 이용하여 해결합니다.

 

첫 루프에서는 prefix products만 구하고, 두 번째 루프에서 suffix products를 구해 prefix products와 곱합니다.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        std::vector<int> products(len, 1);
        int product_left = 1;
        int product_right = 1;

        for(int i=0; i<len; ++i) {
            products[i] = product_left;
            product_left *= nums[i];
        }
        for(int i=len-1; i>=0; --i) {
            products[i] *= product_right;
            product_right *= nums[i];
        }

        return products;
    }
};

 

시간복잡도 : O(n)

공간복잡도 : O(1)