[leetcode] 238. Product of Array Except Self

문제

배열에서 자신을 제외한 나머지 요소의 곱셈 결과를 출력하는 문제.

O(n)에 나눗셈을 하지 않고 풀어야 한다.

 

---

풀이

나눗셈을 하지 않고 O(n)에 풀어야 하니깐 왼쪽 와 오른쪽의 곱셉 결과를 이용하면 된다.result[n] 은 왼쪽의 n-1까지의 곱셈 결과 * 오른쪽 n+1까지의 곱셈 결과이다.

 

인풋이 [-1,1,0,-3,-3] 일 경우 result[2]은 왼쪽부터 1번 요소까지의 곱셈 결과(-1 * 1) *  오른쪽부터 3번 요소까지의 곱셈 결과( 3 * -3)   = -1 * -9 = 9 가 된다.

 

 

---

코드

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

        for (int idx = 0; idx < nums.length; idx++) {
            result[idx] = left;
            left *= nums[idx];
        }


        for (int idx = nums.length - 1; idx >= 0; idx--) {
            result[idx] *= right;
            right *= nums[idx];
        }

        return result;
    }
}

 

 

 

 

---

참고

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