Leetcode - 238. Product of Array Except Self

문제

주어진 배열을 자기자신을 제외한 모든 값을 곱한 값으로 바꾸어라.

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

해결

0이 한개일때, 0이 두개일때의 경우를 제외하고 구간합으로 해결할수 있음.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    int z_cnt = 0;
    int prod = 1;
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == 0) {
            z_cnt++;
            if (z_cnt > 1)
                break;
            continue;
        }
        prod *= nums[i];
    }
    if (z_cnt == 0) {
        for (int i = 0; i < numsSize; i++)
            nums[i] = prod / nums[i];
    } else if (z_cnt == 1) {
        for (int i = 0; i < numsSize; i++) {
            if (nums[i] == 0)
                nums[i] = prod;
            else 
                nums[i] = 0;
        }
    } else {
        for (int i = 0; i < numsSize; i++)
            nums[i] = 0;
    }
    return nums;
}

해결 O(n)

나누기 연산을 사용하지 않는 방법. left -> right 그리고 left <- right 이렇게 two pass로 풀수 있는 신박한 방법 -> 풀이 설명은 여기서 Pramp - Array of Array Products

prod[]  [1]*[2]*[3]   [0]*[2]*[3]   [0]*[1]*[3]   [0]*[1]*[2]
l->r:   1             1*[0]         1*[0]*[1]     1*[0]*[1]*[2]
l<-r:   *[3]*[2]*[1]  *[3]*[2]      *[3]          1

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> prod(nums.size(), 0);
        int temp = 1;
        for (int i = 0; i < nums.size(); i++) {
            prod[i] = temp;
            temp *= nums[i];
        }
        // after that prod[last idx] got a answer
        temp = 1;
        for (int i = nums.size() - 1; i >= 0; i--) {
            prod[i] *= temp;
            temp *= nums[i];
        }
        // after that prod[0] ~ prod[last idx -1] got a answer
        return prod;
    }
};