[LeetCode 238] Product of Array Except Self (Java)

https://leetcode.com/problems/product-of-array-except-self/description/?page=1&search=332

---

풀이

이 문제는 정수 배열 nums가 주어졌을 때, i번째 인덱스의 값이 nums[i]를 제외한 나머지 nums의 원소들의 곱인 배열 answer를 리턴하는 문제이다.

단, 시간복잡도가 $O(N)$이어야하고, 나눗셈을 사용하지 말라고 하였다.

💡 이 문제는 힌트가 문제에 있다. 시간복잡도 제한을 $O(N)$으로 주었는데, 이를 통해 우리는 루프를 중첩시킬 수 없으니, 곱하기를 하더라도 한쪽으로 이동해가며, $n_0 \times n_1 \times \dots \times n_{i-1} \times n_i$처럼 누적해서 곱해질 것이다.

그렇다면, 인덱스가 $0 \sim i - 1$일 때를 하나의 루프에서 구하고, 인덱스가 $i + 1 \sim n - 1$일 때를 또 다른 루프에서 구한 뒤, 둘을 곱하면 nums[i]를 제외한 나머지 nums의 원소들의 곱이 answer[i]에 저장될 것이다.

이를 코드로 옮기면 다음과 같다.

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