[LeetCode] 238 - Product of Array Except Self

문제

• 링크: https://leetcode.com/problems/product-of-array-except-self
• 난이도: Medium
• 태그: 배열, 누적합
• 결과: Time: 0 ms (100%), Space: 40.21 MB (58.90%)

풀이

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n), suffix(n), ans(n);

        prefix[0] = 1;
        for (int i = 1; i < n; i++)
        {
            prefix[i] = prefix[i-1] * nums[i-1];
        }

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

        for (int i = 0; i < n; i++)
        {
            ans[i] = prefix[i] * suffix[i];
        }

        return ans;
    }
};

먼저 이런 풀이를 생각할 수 있다.

• prefix[i]: i기준 왼쪽 원소들의 누적곱
• suffix[i]: i기준 오른쪽 원소들의 누적곱 그러면 ans[i]는 prefix[i] * suffix[i]가 될 것이다.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);

        ans[0] = 1;
        for (int i = 1; i < n; i++)
        {
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) 
        {
            ans[i] *= suffix;
            suffix *= nums[i];
        }

        return ans;
    }
};

조금 더 최적화하면 O(1) 공간으로 풀이할 수 있다. prefix는 nums를 직접 수정해서 저장해버리고, suffix는 원소를 역순으로 순회하여 변수 하나로 해결할 수 있다.

이 포스트는 달레 스터디(2주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.