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

문제 링크: https://leetcode.com/problems/product-of-array-except-self/description/?envType=list&envId=rdlarbki 

Product of Array Except Self - LeetCode

1. 주의할 점

- 원소중에 0이 있다면?

- 원소중에 0이 2개 이상 있다면?

 

2. 구현

- O(N)으로 구현하라고 했으므로 생각했던 방법은 모든 원소들의 곱을 구하고 해당 원소로 나누면 될 것 같았다.(모든 원소들의 곱은 int 범위를 벗어나지 않는다고 문제에 적혀있기 때문)

- 하지만 원소중에 0이 있다면 실수/0 = 무한대가 되어버린다. 그래서 0의 개수(zeroNum)를 따져보기로 했다.

- 0이 1개 있다면, 해당 원소를 제외한 원소들의 곱만 0이 아닌 값을 가지고 나머지는 0을 가진다. 그리고 0이 2개 이상 있다면 당연히 자신을 제외한 모든 원소들의 곱은 0이 된다.

- mulExceptZero의 값에는 0이 아닌 모든 원소들의 곱을, mul에는 모든 원소들의 곱을 저장하도록 구현했다.

 

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int mul = 1,zeroNum=0,mulExceptZero=1;
        for(int i=0;i<nums.size();i++){
            int val = nums[i];
            mul *= val;
            if(val==0) zeroNum++;
            else mulExceptZero *= val;
        }
        vector<int> answer;
        for(int num: nums){
            int initNum = 0;
            if(zeroNum==1 && num==0) initNum = mulExceptZero;
            else if(zeroNum==0) initNum = mul/num;
            answer.push_back(initNum);
        }

        return answer;
    }
};