[leetcode] 238. Product of Array Except self

문제

 

product는 '곱'이라는 뜻이다.

즉, 문제는 자신을 제외한 배열의 곱을 구하라는 뜻이다.

조건은 시간 복잡도는 O(n)이면서 나눗셈을 사용하지 말고 구현하라고 하였다.

 

조건에 맞게 풀기

1. time O(n), space O(2n)

2. timeO(n), space O(1)

 

인덱스 i의 product array except self을 구하면

nums[0] * nums[1] * .... * nums[i -1]      *      nums[i + 1] * nums[i + 2] * .... * nums[n - 1]

 

앞 부분과 뒷 부분으로 나누어 메모를 한 후 필요한 값을 꺼내 쓸 수 있다.

각각 앞, 뒤로 1을 추가해서 곱셈 진행할 수 있도록 한다.

 

참고 사이트

알고달레

 

1. time O(n), space O(2n)

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int size = nums.length;
        
        int[] before = new int[size + 1];
        before[0] = 1;
        for(int i = 0; i < size; i++) {
            before[i + 1] = before[i] * nums[i];
        }

        int[] after = new int[size + 1];
        after[size] = 1;
        for(int i = size - 1; i > -1; i--) {
            after[i] = after[i + 1] * nums[i];
        }

        int results[] = new int[size];
        for(int i = 0; i < size; i++) {
            results[i] = before[i] * after[i + 1];
        }
        return results;
    }
}

 

2. time O(n), space O(1)

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

        int results[] = new int[size];
        int num = 1;
        results[0] = 1;
        for(int i = 1; i < size; i++) {
            num *= nums[i - 1];
            results[i] = num;
        }

        num = 1;
        for(int i = size - 1; i > 0; i--) {
            num *= nums[i];
            results[i - 1] *= num;   
        }

        return results;
    }
}

 

조건에 어긋나지만 풀 수는 있는 방법

1. time O(n^2), space O(1)

2. 나눗셈을 사용하면 시간 복잡도 O(n)으로 풀 수 있다. 대신 0에 대한 처리가 필요하다.

이 경우 0이 하나일 경우 따로 0을 곱하지 않았을 때의 값, 전체를 곱한 값을 각각 하나 저장해둬서 풀 수 있다.

(대신 0이 둘 이상일 경우 이 조건은 성립하지 않는다.)

 

O(n^2), time limit

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int size = nums.length;
        int[] results = new int[size];
        for(int i = 0; i < size; i++) {
            int result = 1;
            for(int j = 0; j < size; j++) {
                if (i == j) continue;
                result *= nums[j];
            }
            results[i] = result;
        }
    
        return results;
    }
}

 

Using Division operation

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int size = nums.length;
        int[] results = new int[size];
        
        int zeroCount = 0;
        int result = 1;
        int resultContainsZero = 1;
        for(int i = 0; i < size; i++) {
            if (nums[i] == 0 && zeroCount == 0) {
                zeroCount++;
                resultContainsZero *= nums[i];
                continue;
            }
            
            result *= nums[i];
            resultContainsZero *= nums[i];
        }

        for(int i = 0; i < size; i++) {
            if (nums[i] == 0) {
                if (zeroCount == 1) {
                    results[i] = result;
                } else {
                    results[i] = 0;
                }
            }
            else {
                results[i] = resultContainsZero / nums[i];
            }
        }
    
        return results;
    }
}