LeetCode #238. 자기 자신을 제외한 배열의 곱

Source: Dev.to

나눗셈을 이용한 풀이

시간 복잡도: O(n) – 배열을 두 번 선형으로 탐색합니다.
공간 복잡도: O(1) 보조 공간 (몇 개의 추가 변수만 사용).

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

        int zeroCount = 0;
        int product = 1;

        // First pass: compute product of non‑zero elements and count zeros
        for (int num : nums) {
            if (num == 0)
                zeroCount++;
            else
                product *= num;
        }

        // Second pass: fill the result array based on zero count
        for (int i = 0; i < n; i++) {
            if (zeroCount > 1) {
                result[i] = 0;
            } else if (zeroCount == 1) {
                result[i] = (nums[i] == 0) ? product : 0;
            } else {
                result[i] = product / nums[i];
            }
        }

        return result;
    }
}

나눗셈 없이 두 번 통과하는 풀이

이 방법은 앞쪽(prefix)과 뒤쪽(suffix) 곱을 이용해 현재 요소를 제외한 모든 요소의 곱을 계산합니다.

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

        // Prefix product: result[i] holds product of all elements to the left of i
        result[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }

        // Suffix product: multiply by product of elements to the right of i
        int suffix = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            result[i] *= suffix;
            suffix *= nums[i];
        }

        return result;
    }
}