[C++/Algorithm] Product of Array Except Self - leetcode

[neetcode.io roadmap project] - Arrays & Hashing

아래는 leetcode 238. Product of Array Except Self를 푼 흐름입니다.

0. 문제의 이해

nums vector(문제의 Input)이 주어질 때,
result vector(문제의 Output)의 i 번째 index는
nums 배열의 i번째 인덱스를 제외한 모든 원소를 곱한 값이 되도록 해야합니다.
이때, 알고리즘을 O(n)의 시간복잡도로 동작하도록 하는 것이 어려운 부분입니다.

예를 들어 nums = [1, 2, 3, 4]라면 result = [24, 12, 8, 6]이 되어야 합니다.

---

1. Runtime 27ms(상위 30%) // Memory 14 MB(상위 40%) 풀이

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

위 풀이의 핵심은 알고리즘을 O(n)시간에 동작하게 하기 위해 nums vector을 단 2번만 순회한다는 것입니다.
이것을 가능하게 하는 발상은, 곱셈의 결과를 result vector에 바로 저장하는 것입니다.

---

첫 번째 순회 시에는 nums vector의 i번째 index 이전의 값들을 모두 곱한 값을 result vector의 i번째 index에 저장합니다.
이를 위해서 result vector의 i번째 index에 result[i-1]과 nums[i-1]을 곱한 값을 넣습니다.

두 번째 순회 시에는 nums vector의 i번째 index 이후의 값들을 모두 곱한 값을 result vector의 i번째 index의 값과 곱해줄 것입니다.

이 때, 주의할 점은 새로운 변수를 생성한 후 nums vector의 i번째 index 이후의 곱의 값을 따로 저장해야한다는 점입니다.
첫 번째 순회 처럼 result[i+1]와 nums[i+1]의 곲을 result[i]에 곱해준다면 result[i]가 result[i+1]에 곱해진 상태이므로 올바른 상황이 아닙니다.

이를 통해 nums vector의 i번째 index 이전과 이후의 곱이 result vector의 i번째 index에 저장됨으로써 문제의 조건이 성립합니다.

아래의 그림을 통해 쉽게 표현해 보겠습니다.

---

2. Conclusion

위 문제를 통해서 배울 수 있었던 점은

• 각 result[i]를 구하기 위해 nums를 한번씩 모두 순회하는 것이 아닌, nums[i-1]이전, nums[i+1]이후로 나누어 각각 곱해준다는 발상

입니다.