[알고리즘] 리트코드 238. Product of Array Except Self c++ // 배열, 누적곱, rbegin, partial_sum

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

* 풀이1(케이스 분류)

경우의수를 나누고구현

i) 0의갯수가 0개인경우

ii) 0의갯수가 1개인경우

iii) 0의갯수가 2개이상인경우

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ret;
        int zero_count=0;
        int total_product=1;
        for(auto num : nums){
            if(num==0) zero_count++;
            else total_product*=num;
        }

        for(auto num : nums){
            if(zero_count==0){
                ret.push_back(total_product/num);
            }
            if(zero_count==1){
                if(num==0){
                    ret.push_back(total_product);
                }
                else{
                    ret.push_back(0);
                }
            }
            if(zero_count>=2){
                ret.push_back(0);
            }
        }
        return ret;
    }
};

 

 

* 풀이 2 (누적곱 이용)

나를제외한곱 == 내앞의누적곱 * 내뒤의 누적곱

 

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> pre=nums;
        vector<int> suf=nums;
        vector<int> ret(nums.size());
        //pre배열의 누적곱을 pre에 담기 , (multiplies안쓰면 누적합)
        //원본배열과 결과배열의 크기는 같아야함에 주의
        partial_sum(pre.begin(),pre.end(),pre.begin(), multiplies<int>());
        //rbegin => 뒤에서부터 순회
        partial_sum(suf.rbegin(),suf.rend(),suf.rbegin(), multiplies<int>());

        //idx의 범위를체크하고, 범위밖인경우 1을 곱함
        for(int i=0;i<nums.size();++i){
            ret[i] = (i ? pre[i-1] : 1) * (i+1 < nums.size() ? suf[i+1] : 1);
        }

        return ret;
    }
};

 

* rbegin, partial_sum

뒤부터 순회하는 rbegin, rend

 

partial_sum(pre.begin(),pre.end(),pre.begin());

누적합을구해서 pre에 넣음

partial_sum(pre.begin(),pre.end(),pre.begin(), multiplies<int>());

누적곱을구해서 pre에 넣음

partial_sum(suf.rbegin(),suf.rend(),suf.rbegin(), multiplies<int>());

suf의 뒤부터 순회하면서 / 누적곱을구해서 suf의 뒤부터 채워넣음