[Leetcode] 238. Product of Array Except Self (C++)

문제

238. Product of Array Except Self

코드

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) { 
        vector<int> left(nums.size(), 1);
        
        for(int i = 1; i < nums.size(); i++){
            left[i] = nums[i-1] * left[i-1];
        }
        
        int R = 1;
        for(int i = nums.size()-1; i >= 0; i--){
            left[i] *= R;
            R *= nums[i];
        }
        return left;
    }
};

접근

자기 자신을 제외한 모든 원소들의 곱을 구해야 하기 때문에 누적 곱을 유지해야할 것 같았다. 따라서 자기 이전까지의 곱을 유지하는 left라는 벡터를 유지했다. 이후 역순으로 살펴보면서 자기 오른쪽 값들의 곱을 유지했다.