[Codility] Product of Array Except Self

문제

 

분석

• 자기 자신을 제외한 값들의 곱을 구하는 것이다.
• O(n) 으로 구현을 해야 된다
• 나눗셈 연산을 쓰지 말하야 한다.
• 해당 인덱스를 기준으로 왼쪽 을 곱한 값, 오른 쪽 값을 곱한 값을 저장한다.
• 왼쪽 오른쪽 값을 계산한다.
• 이렇게 하는 이유는 O(n) 으로 풀어야 하기 떄문이다.

 

구현

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int []leftNums = new int[n];
        int []rightNums = new int[n];
        int []answer = new int[n];
        leftNums[0] = 1;
        
        for(int i = 1; i < n; i++) {
           leftNums[i] = nums[i-1] * leftNums[i-1];
        }
        rightNums[n-1] = 1;
        for(int i = n-2; i >= 0; i--) {
            rightNums[i] = nums[i+1] * rightNums[i+1];
            answer[i] = rightNums[i] * leftNums[i];
        }
        answer[n-1] = rightNums[n-1] * leftNums[n-1];
        return answer;
    }
}

 

 

결과

 

 

문제

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

Product of Array Except Self - LeetCode