LeetCode 238 - Product of Array Except Self

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

 

int [ ] answer;

answer [i] = nums에서 i 위치를 제외한 모든 원소의 곱

O(n)의 시간복잡도와 나눗셈 연산 없이 해결해야 한다.

가장 쉬운 방법은 모든 원소의 곱을 구하고 순회하며 나눗셈 연산을 하는 것이다.

하지만 나눗셈은 사용하면 안 되는 조건이 있다.

그렇다면 자신을 제외한 왼쪽곱, 오른쪽곱의 배열을 만들어 두 배열의 값을 곱해서 반환하면 된다.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] left = new int[nums.length];
        Arrays.fill(left, 1);
        int p = 1;
        for (int i = 1; i < nums.length; i++) {
            left[i] = p * nums[i - 1]; 
            p *= nums[i - 1];
        }
        
        p = 1;
        int[] right = new int[nums.length];
        Arrays.fill(right, 1);
        for (int i = nums.length - 2; i >= 0; i--) {
            right[i] = p * nums[i + 1];
            p *= nums[i + 1];
        }

        int[] answer = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            answer[i] = left[i] * right[i];
        }

        return answer;
    }
}

그런데 위의 풀이를 보면 left, right, answer라는 추가 공간이 많이 사용됐다.

생각해 보면 그냥 answer 배열 하나에 다 처리를 해도 될 것 같다.

또한 배열을 1로 채워주고 있는데 시작 지점만 채워주면 된다.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

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

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

        return answer;
    }
}