[LeetCode] 238. Product of Array Except Self

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

Product of Array Except Self - LeetCode

Product of Array Except Self - Medium

 

배열에서 자기자신을 제외한 모든 수를 곱한 수들을 구하는 문제다.

 

처음에는 뭐야 쉽네 하며 0을 제외한 모든 수를 곱한 수 p를 저장하고,

0의 개수를 저장한 뒤,

0의 개수가 2개 이상이면 모두 0,

0의 개수가 1개라면 nums[i]==0 인 경우엔 p, 나머지는 0

0의 개수가 없다면 p/nums[i]로 구했다가

뒤늦게 without using the division operation 이라는 글귀를 발견했다.

 

이미 division operation이 머릿속에 깊게 박혀 다른 해결방안을 찾지 못해  결국 Discussion을 참고하였다.

https://leetcode.com/problems/product-of-array-except-self/discuss/1597959/c%2B%2B-or-discussing-all-solutions-or-explaining-in-detail-with-image-or

RP (right production) 배열을 하나 만든다.

RP의 식은 RP[nums.size()-1] = 1 이고, RP[i] = RP[i+1] * nums[i+1] 이 된다.

이러면 RP에 저장된 식들은 nums[i]의 오른쪽에 있는 모든 수를 곱한 값이 된다.

그러면 이제 왼쪽에 있는 모든 수를 곱한 값을 구해주면 될 것이다.

RP[0]는 nums[0]를 제외한 모든 수를 곱한 수와 같으므로, 1을 곱해주면 되고, RP[1]는 nums[1]만, RP[2] = nums[1]*nums[2],... 이렇게 곱해주면 된다.

따라서 LP는 배열이 아닌 그냥 int로 처음에 1로 둔후, RP[i] *= LP, LP*=nums[i] 로 식을 완성시켜 주면 된다.

 

전체 풀이 코드

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