[Leetcode][PrefixSum] Merge Intervals 풀어보기

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

 

 

오늘의 문제는 누적합을 사용하는 문제입니다. 실제로 따지고 보면 합은 아니지만 형태는 그런 방식입니다.

각 answer[i]에는 본인 nums[i]를 제외한 나머지 모든 값을 곱한 결과를 저장해야합니다. 

 

문제의 조건은 O(n)의 복잡도를 사용하면서 division operation을 사용하지 않는것입니다.

만약 division을 사용할 수 있다면, 모두 곱하고 필요한 값만 나누면 되기 때문에 매우 쉽게 해결할 수 있는데 이 경우를 회피하기 위함인것으로 보입니다. 

 

본인 외의 모든 값을 곱하는 것을 반복한다면 쉽게 결과를 얻을 수 있겠지만 이 경우는 O(n^2)가 됩니다.

 

현재 위치에서의 왼쪽, 오른쪽을 나눠 누적곱을 미리 저장해놓는다면 O(n)으로도 해결이 가능할 것입니다.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int N = nums.size();
        vector<int> leftproduct(N, 0);
        vector<int> rightproduct(N, 0);

        leftproduct[0] = 1;
        rightproduct[N-1] = 1;

        for (int i = 1; i < N; ++i)
        {
            leftproduct[i] = leftproduct[i - 1] * nums[i - 1];
        }

        for (int i = N-2; i >= 0; --i)
        {
            rightproduct[i] = rightproduct[i + 1] * nums[i + 1];
        }

        vector<int> output(N, 0);
        for (int i = 0; i < N; ++i)
        {
            output[i] = leftproduct[i] * rightproduct[i];
        }

        return output;
    }
};

 

사용하는 저장공간을 줄이는 시도도 가능하겠습ㄴ디ㅏ.