Intuition

Prefix Sum? (누적합)

나열된 수의 누적된 합을 말한다.
배열의 일부 구간에서 대한 합을 매우 빠르게 구할 수 있게 해준다. N개의 원소로 이루어진 배열이 주어졌을 때 반복문을 통해 부분 배열의 합을 구하려면 O(N)이 걸리는데, 누적합을 이용하면 부분합을 0(N+M)으로 구할 수 있다.  

Examples:

Input: arr[] = [10, 20, 10, 5, 15]
Output: 10 30 40 45 60
Explanation: For each index i, add all the elements from 0 to i:
prefixSum[0] = 10, 
prefixSum[1] = 10 + 20 = 30, 
prefixSum[2] = 10 + 20 + 10 = 40 and so on.

Input: arr[] = [30, 10, 10, 5, 50]
Output: 30 40 50 55 105
Explanation: For each index i, add all the elements from 0 to i:
prefixSum[0] = 30, 
prefixSum[1] = 30 + 10 = 40,
prefixSum[2] = 30 + 10+ 10 = 50 and so on.

그림을 그려보니...

피라미드 모양이 대칭적으로 보인다.

1|2|3|4

 |2|3|4
1| |3|4
1|2| |4
1|2|3|

위의 모습을 갖춘 곱셈들을 만들어야 한다는 생각과 Prefix sum에 대한 생각이 맞물려 정방향 Prefix product와 반대방향 Prefix product를 만들어 각 인덱스에 있는 값들을 곱하면 되겠다는 생각을 하게 되었다.

답안 1

class Solution {
    public int[] productExceptSelf(int[] nums) {

        int[] prefixProduct = getPrefixProduct(nums);
        int[] prefixProductReverse = getPrefixProductReverse(nums);
        int[] resultArray = new int[nums.length]; 

        for (int i = 0; i < resultArray.length; i++) {
            resultArray[i] = prefixProduct[i] * prefixProductReverse[prefixProductReverse.length - (i + 1)];
        }

        return resultArray; 
    }

    public int[] getPrefixProduct(int[] nums) {
        int[] resultArray = new int[nums.length];
        resultArray[0] = 1; 
        int i = 0;
        while (i + 1 < resultArray.length) {
            resultArray[i + 1] = resultArray[i] * nums[i];
            i += 1; 
        }

        return resultArray;
    }

    public int[] getPrefixProductReverse(int[] nums) {
        int[] resultArray = new int[nums.length];
        resultArray[0] = 1; 
        int i = 0;
        while (i + 1 < resultArray.length) {
            resultArray[i + 1] = resultArray[i] * nums[nums.length - (i + 1)];
            i += 1; 
        }

        return resultArray;
    }
}

두개의 배열을 만들고 3번 pass하는 것은 너무 오래 걸린다. 그러므로 하나의 배열만 사용해 먼저 Prefix product를 만들고 다음에 반대 방향으로 suffix product들을 곱해줘 최적화 할 수 있다.

result[0] = 1
result[1] = 1 * 1 = 1
result[2] = 1 * 1 * 2 = 2
result[3] = 1 * 1 * 2 * 3 = 6

반대 방향을 곱해주기 

result[3] = result[3] * 1 = 6
result[2] = result[2] * 1 * 4 = 8
result[1] = result[1] * 1 * 4 * 3 = 12
result[0] = result[0] * 1 * 4 * 3 * 2 = 24

답안 2

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] resultArray = new int[nums.length]; 
        resultArray[0] = 1; 

        for (int i = 0; i < resultArray.length - 1; i++) {
            resultArray[i + 1] = resultArray[i] * nums[i]; 
        }

        int suffix = 1; 

        for (int i = resultArray.length - 1; i >= 0; i--) {
            resultArray[i] = resultArray[i] * suffix;
            suffix *= nums[i];
        }

        return resultArray;
    }
}