[LeetCode] 238. Product of Array Except Self

문제

1차원 배열 nums가 주어졌을 때, 다음을 만족하는 배열 answer를 리턴하라.

answer[i]는 nums[i]를 제외한 요소의 모든 곱이다.

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

Product of Array Except Self - LeetCode

풀이

나누기 연산을 사용하지 않는 조건이기 때문에, 다른 방법을 생각해야 한다.

각 answer[i] 마다 nums[i]를 제외한 요소들을 모두 곱하는 경우 O(n*n)으로 Time Limit Exceeded가 된다.

 

배열 nums가 [1, 2, 3, 4]인 경우 nums [i]를 제외한 요소들을 확인해보자.

answer[1]는 2의 left에 있는 [1]과 right에 있는 [3, 4]를 곱한 수이고

answer[2]는 3의 left에 있는 [1, 2]과 right에 있는 [4]를 곱한 수이다.

 

left만 확인해보면 answer[1] = 1, answer[2] = 1*2, answer[3] = 1*2*3 인 것을 볼 수 있다.

다시 말해서, answer[i] = answer[i - 1] * nums[i - 1] 가 된다.

answer[0]은 left가 없기 때문에 1을 대입하면 된다.

 

right만 보면 answer[2] = 4, answer[1] = 4*3, answer[0] = 4*3*2 이다.

다시 말해서, answer[i] = answer[i + 1] * nums[i + 1] 가 된다.

 

따라서 left와 right를 곱한 값을 answer에 저장하는 것이므로

left를 answer[i]에 각각 저장하고

right는 따로 right 변수를 하나 생성하여 answer[i]에 right를 곱하고, 그다음 계산을 위해 right *= nums[i]를 하며 반복하면 된다.

 

코드

public class leetcode_238 {
    static public int[] productExceptSelf(int[] nums) {

        int len = nums.length;
        int[] answer = new int[len];

        answer[0] = 1;
        for (int i = 1; i < len; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
            System.out.println(answer[i]);
        }

        int right = 1;
        for (int i = len - 1; i >= 0; i--) {
            answer[i] *= right;
            right *= nums[i];
        }

        return answer;
    }

    public static void main(String[] args) {
        int[] temp = {1, 2, 3, 4};
        System.out.println();
        for (int num : productExceptSelf(temp)) {
            System.out.println(num);
        }
    }

}