[리트코드] 238. Product of Array Except Self <Java>

문제

---

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

Product of Array Except Self - LeetCode

 

현재 인덱스의 수를 제외한 나머지 수들의 곱을 연산하는 문제( 단, 나눗셈 연산을 사용하지 않는다.)

 

 

풀이

---

문제의 조건이 없다면 모든 nums 배열의 수를 곱한 뒤 현재수를 나누기를 해주면 쉬운 문제지만, 나눗셈 연산을 하지않고 푸는 문제기 때문에 나눗셈 연산없이 풀어본다.

 

 

알고리즘 순서

1. 왼쪽에서 오른쪽으로 차례대로 수를 곱해 저장한다.
2. 오른쪽에서 왼쪽으로 차례대로 수를 곱해 저장한다.
3. 현재 위치 인덱스가 i 라 했을 때, 왼쪽에서 i-1 까지의 곱 * 오른쪽에서 i+1 까지의 곱 연산을 해준다.

 

위의 순서대로 두개의 곱을 저장한 DP 배열을 가지고 풀면 쉽게 해결할 수 있다.

<전체 코드>

class Solution {
    public int[] productExceptSelf(int[] nums) {
        // 본인을 제외한 나머지들의 곱 리스트 반환, 나누기 연산 없이
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        
        left[0] = nums[0];
        for(int i = 1 ; i < n; i++){
            left[i] = left[i - 1] * nums[i];
        }
        
        right[n - 1] = nums[n - 1];
        for(int i = n - 2 ; i >= 0 ; i--){
            right[i] = right[i + 1] * nums[i];
        }
        
        int[] answer = new int[n];
        answer[0] = right[1];
        answer[n - 1] = left[n -2];
        for(int i = 1 ; i < n - 1 ; i++){ 
            answer[i] = left[i-1] * right[i+1];
        }
        
        return answer;
    }
}