[리트코드] 238. Product of Array Except Self

문제 :

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

Product of Array Except Self - LeetCode

 

분석 :

이 문제는 구간곱 문제다

조금 푸는 방법이 신기해서 기록해보려구 한다!! (절대 생각도 못한 방법 .. ㅠ)

 

처음엔 

자기 자신을 제외한 곲이라 해서 

1. nums 배열을 복사한 copy한 배열 생성

2. 배열 내 모든 곲을 곱한 뒤 제외한 index 위치에 값을 저장

으로 생각했는데 1번과 2번이 이중 for문으로 문제에서 주어진 O(n) 시간 복잡도를 만족시킬 수 없었다.

 

코드에 대한 설명은 

https://leetcode.com/problems/product-of-array-except-self/discuss/793722/C%2B%2B-Easy-Solution-Meeting-All-Requirements-Explained-~98-Time-95-Space

이분의 설명을 보고 작성하였다.

 

우선 왼쪽으로 돌면서 

res 배열의 이전값과 nums 배열의 이전값을 곱한 값으로 res 배열을 초기화 해준다.

 

예를 들어서 [1,2,3,4,5,6] 배열이 있을때

각 배열의 값은 

이렇게 구성이 되는데 밑줄친 값은 res 배열의 이전 값이다. 값은 nums 배열 인덱스에 해당되는 값 전까지의 곲으로 계산되었고 마지막 인덱스는 결과값과 같은 것을 확인 할수 있다.

 

그리고 이제는 res 의 4번째 인덱스부터 거꾸로 값을 계산한다. 어떻게 하나면은 미리 nums 배열의 마지막 값인 prod 를 곱해주고 prod 값을 해당 index의 nums 값을 곱해 누적시켜준뒤 이를 res 배열에 곱해준다.

 

그러면 어떤 효과가 일어나냐면

거꾸로 자기 자신의 nums 값을 제외한 오른쪽부터의 값이 곱해지는 걸 확인 할수 있다.

 

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        
        // setting up the necessary variables
        int len = nums.size(), prod = nums[len - 1];
        vector<int> res(len);
        // ruling out an edge case
        if (!len) return res;
        // initialising res and using it for the first pass
        res[0] = 1;
        // each cell will be the product of the previous and the matching previous value in nums
        for (int i = 1; i < len; i++) res[i] = res[i - 1] * nums[i - 1];
        // second pass, from the right
        for (int i = --len - 1; i >= 0; --i) {
            res[i] *= prod;
            prod *= nums[i];
            // cout << "res " << res[i] << '\n';
            // cout << "prod " << prod << '\n';
        }
        return res;
        }
};

 

 

개념은 같지만 이를 풀어내는 방식에서 정말 획기적인 방식인거 같다 ..!