[array] product of array except self

✅ Problem

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

 

✅ Approach & Solution

방식1) 시간복잡도 : O(n)

• 자기 자신을 제외하고 자신의 왼쪽 곱셈 결과와 오른쪽 곱셈 결과 곱하기

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

        // 자기 자신의 왼쪽 곱셈 결과 포함시키기
        int p = 1; // 자기 자신은 제외시켜야 하므로 1로 초기화
        for (int i = 0; i < nums.length; i++) {
            result[i] = p;
            p *= nums[i];
        }

        // 자기 자신의 오른쪽 곱셈 결과 포함시키기
        p = 1; // 자기 자신은 제외시켜야 하므로 1로 초기화
        for (int i = nums.length - 1; i >= 0; i--) {
            result[i] *= p;
            p *= nums[i];
        }

        return result;
    }
}

 

방식2) 시간복잡도 : O(n)

• 참고) 문제 조건에서 나눗셈 사용하지 말라고 했기 때문에 해당 방식은 정답 X
• 미리 전체 곱셈 값을 구한 후 각 항목별로 자기 자신을 전체 곱셈 값에서 나눔
  • 전체 곱셈 값 구하기
    • 0이 존재하지 않을 때 : 모든 원소 대상 곱셈 값 계산
    • 0이 1개 존재할 때 : 0 제외한 곱셈 값 계산
    • 0이 2개 이상 존재할 때 : 곱셈 값 무조건 0
  • 항목별 곱셈 값 구하기
    
    • 0이 존재하지 않을 때 : 전체 곱셈 값에서 자기 자신 나누기
    • 0이 1개 존재할 때 : 자신이 0일 때만 전체 곱셈 값, 나머지는 모두 0
    • 0이 2개 이상 존재할 때 : 무조건 0

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

        int zeroCnt = 0;
        for (int i : nums) {
            if (i == 0) {
                zeroCnt += 1;
            }
        }

        int productResult = 1;
        if (zeroCnt == 0) {
            for (int i : nums) {
                productResult *= i;
            }
        } else if (zeroCnt == 1) {
            for (int i : nums) {
                if (i != 0) {
                    productResult *= i;
                }
            }
        } else {
            productResult = 0;
        }

        if (zeroCnt == 0) {
            for (int i = 0; i < nums.length; i++) {
                result[i] = productResult / nums[i];
            }
        }

        if (zeroCnt == 1) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == 0) {
                    result[i] = productResult;
                }
            }

        }

        return result;
    }
}