[LeetCode] 238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/?envType=study-plan-v2&envId=top-interview-150 

Product of Array Except Self - LeetCode

문제 유형 : 배열

문제 난이도 : Medium

 

문제

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.

 

배열 nums가 주어집니다. 배열의 i번째 수가 nums배열의 i번째 수를 제외한 모든 수를 곱한 요소를 가진 배열을 반환하시오. 선형 시간으로 풀어야 하고, 나눗셈 사용은 금지되어 있습니다.(테스트 케이스에 0이 들어가서 오류가 나게 되어있습니다)

 

풀이

자신을 제외한 왼쪽 곱을 누적시킨 배열 left와 오른쪽 곱을 누적시킨 배열 right을 만듭니다.

[1,2,3,4]를 예로 들었을 때,

left는 [1, 1, 2, 6], right는 [24, 12, 4, 1]이 됩니다.

그리고 두 값을 곱하면 양쪽에서 자신을 제외하고 곱한 값이 나옵니다.

 

코드(C++)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        const int n = nums.size();
        vector<int> left(n, 1), right(n,1), products(n);
        for(int i = 1; i < n; i++){
            left[i] = nums[i-1] * left[i-1];
        }

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

        for(int i = 0; i < n; i++){
            products[i] = left[i] * right[i];
        }

        return products;
    }
};