리트코드 자기를 제외한 배열의 곱 c++ // 누적곱 해결방법 : 누적곱 테이블을 정의하라

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

1. 기존코드

0을 제외한 총 곱을 구하고

0이 몇개인지에 따라서 분기함.. 너무 복잡함

typedef long long ll;
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> v,zero;
        int ret=1, iszero=0,isallzero=1; //0을제외한 총곱 , 0이있는지, 모두0인지
        for(auto num:nums){
            if(num==0) {
                iszero=1;
                zero.push_back(num);
                continue;
            }
            isallzero=0;
            ret*=num;
        }
        if(zero.size()==nums.size()){ //모두0인경우
            for(int i=0;i<nums.size();++i){
                v.push_back(0);
            }
            return v;
        }

        if(iszero)
            for(auto num:nums){
                if(num==0){
                    //cout<<ret<<" ";
                    if(zero.size()>=2) //0이 2개이상인경우
                        v.push_back(0);
                    else
                        v.push_back(ret);
                }
                else
                    v.push_back(0);
            }
        else
            for(auto num:nums){
                v.push_back(ret/num);
            }
        return v;
    }
};

 

2. 개선 (누적곱 이용)

0. 테이블정의

left[i] : i를 제외한 i의 좌측곱

right[i] : i를 제외한 i의 우측곱

1. 그림을 보고 식을 작성한후

2. 둘이 곱하면 나를 제외한 좌우측의 곱과 같다.

3. 전체코드

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> left(n+4,1); //(크기,값)
        vector<int> right(n+4,1); //(크기,값)
        vector<int> ret;

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

        return ret;
    }
};

 

3. 추가개선 (메모리절약)

여기서 right 배열을 쓰는대신, right변수를 나를 제외한 우측곱으로 정의한다.

1. left는 똑같이 구한다.

2. 정답 = left * right하면 된다.

right = right * num으로 갱신시켜준다.

3. 전체코드

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> ret(n,1);
        for(int i=1;i<n;++i){
            ret[i]=nums[i-1]*ret[i-1];
        }
        int right=nums[n-1]; //내 우측의 누적곱
        for(int i=n-2;i>=0;--i){
            ret[i]*=right; //좌측곱(ret[i]) * 우측곱 하면 답임!
            right*=nums[i];
        }
        return ret;
    }
};