[LeetCode] C++ 238. Product of Array Except Self

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

 

문제

 

문제 분석

1. 가장 빠른 풀이는 0이 2개 이상 나오는 경우 예외 케이스 처리해주고, 전체 곱을 구하고 각 요소로 나누는 것일 겁니다.

하지만 문제 조건에 without using the division operation이라고 나와있기 때문에 이 방식은 옳지 않습니다.

2. 왼쪽에서 시작해서 쭉 곱한 값과 오른쪽에서 시작해서 쭉 곱한 값을 구해서 두 배열 안의 값들을 매칭해서 곱하면 됩니다.

즉, 해당 인덱스의 왼쪽에 있는 것들을 모두 곱한 값, 오른쪽에 있는 것들을 모두 곱한 값을 따로 구하고 두 값들을 곱해서 최종 값을 구하면 이는 본인을 제외한 나머지 값들을 모두 곱한 값이 됩니다. 예를 들어 Example1의 경우, leftResult = [1, 1, 2, 6], rightResult = [24, 12, 4, 1] 입니다. 각각 맨 왼쪽과 오른쪽에 1을 시작하여야 합니다. (양 끝에서는 각각 왼쪽값, 오른쪽 값이 존재하지 않기 때문에 1로 넣어야 함)

 

풀이

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int leftStartNum = 1;
        int rightStartNum = 1;
        int maxIndex = nums.size() - 1;
        vector<int> leftResult, rightResult, result;
        
        leftResult.push_back(leftStartNum);

        for(int i = 0; i < maxIndex; ++i){
            leftResult.push_back(leftStartNum *= nums[i]);    
        }

        rightResult.push_back(1);

        for(int i = maxIndex; i > 0; --i){
            rightResult.push_back(rightStartNum *= nums[i]);
        }

        for(int i = 0; i <= maxIndex; ++i){
            result.push_back(leftResult[i] * rightResult[maxIndex - i]);
        }

        return result;
    }
};