LeetCode - Product of Array Except Self

문제 설명

1이상의 수가 들어간 정수의 배열이 Input으로 주어진다.
각각의 output[i] 는 input[i]를 제외한 나머지의 곱으로 채워진다.

output을 구하여라

라는 것이 문제다

조건이 있다

나눗셈을 사용하지말고 풀 것 && $O(n)$ 시간 내로 풀 것

해결 방법

나눗셈을 사용하지 않고 푼다는 것이라..
해결방법이 떠오르지 않았다.
아니 $O(n^2)$ 방식과 나눗셈을 이용한 $O(n)$ 방식 밖에 떠오르지 않았다.

그래서 답을 봤는데 신박했다.
사람은 역시 수학을 잘해야 한다고 느꼈다..

암튼 해결방법은 다음과같다.

input과 같은 크기의 배열 L과 R을 준비한다.
L은 왼쪽에서부터 자기의 수를 제외한 이전 수의 곱을 더해가며 진행하고
R은 오른쪽에서부터 자기의 수를 제외한 이후의 수의 곱을 더해가며 진행된다.

따라서 L과 R을 곱하면 $2*N$ 시간만에 해결이 되는 것이다.

코드

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

결과