[leetcode] Product of Array Except Self

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

Product of Array Except Self - LeetCode

 

인덱스 위치의 요소를 제외한 모든 요소를 곱한 결과를 구하는 문제입니다. 

[1,2,3,4] 배열이 주어졌다면, [ 2*3*4, 1*3*4, 1*2*4, 1*2*3 ]으로 반환합니다.

제가 구현한 코드입니다. 저는 모든 요소를 곱한 뒤, 각 요소로 나눠주면 되지 않을까.. 하는 생각으로 코드를 구현했습니다. 

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

        int product = 1;
        int productExceptZero = 1;
        int zeroCount = 0;
        for (int i = 0; i < nums.length; i++) {
            product *= nums[i];
            if(nums[i] != 0){
                productExceptZero *= nums[i];
            }else{
                zeroCount++;
            }
        }

        if(zeroCount > 1){
            return answer;
        }

        for (int i = 0; i < answer.length; i++) {


            if(nums[i] == 0){
                answer[i] = productExceptZero;
            }else{
                answer[i] = product / nums[i];
            }
        }

        return answer;
    }
}

아래는 다른 방식의 풀이입니다. 

https://leetcode.com/problems/product-of-array-except-self/discuss/1584842/java-solution

왼쪽 방향부터 차례로 값을 곱해서 저장하고, 그 결과에 오른쪽 방향부터 값을 곱해서 저장하는 방식입니다. 

주어진 배열 : [ 1, 2 ,3 , 4, 5]

왼쪽부터 곱한 결과를 저장 : [ (1), 1, 1*2, 1*2*3, 1*2*3*4]

오른쪽부터 곱한 결과를 추가로 저장 : [ (1*)2*3*4*5, 1*3*4*5, 1*2*4*5, 1*2*3*5, 1*2*3*4]

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