LeetCode) product-of-array-except-self

문제링크 : https://leetcode.com/problems/product-of-array-except-self/description/

 

쉬운 문제라고 생각했다.

You must write an algorithm that runs in O(n) time and without using the division operation.
를 보기 전까지는.

 

 

내가 작성한 코드는 아래와 같다.

var productExceptSelf = function (nums) {
    const result = Array(nums.length);

    let temp = 1;
    for (let i = 0; i < nums.length; i++) {
        result[i] = temp;
        temp *= nums[i]
    }

    temp = 1
    for (let i = nums.length - 1; i >= 0; i--) {
        result[i] *= temp;
        temp *= nums[i]
    }

    return result;
};

 

 

 

임의의 숫자배열 [ a, b, c, d, e, ... ] 가 있을 때 선택된 임의의 인덱스의 요소를 제외한 나머지 숫자의 곱은 
(전체 배열 요소의 곱 / 해당 요소의 값) 으로 생각하는게 가장 직관적이지만, 문제에서 나눗셈을 금지시켰기 때문에 다른 방식으로 생각해야 했다.

 

 

임의의 요소를 제외한 나머지 숫자의 곱은, 선택퇸 요소 기준으로 이전 모든 요소들의 곱과 이후 모든 요소들의 곱을 곱한 값과 같다. ex ) (a * b * c * d * e * ...) / c = (a * b) * (d * e * ...)

 

 

위 특성을 이용하여 아래와 같이 해결하였다.

1. 입력된 배열 순회를 정방향으로, 그리고 역방향으로 두번 하려고 한다(o(n)).
2. 정방향으로 순회하면서 이전 요소들의 곱을 결과 배열에 할당한다 (a * b).
3. 반대로 역방향으로 순회하면서 이전 요소들의 곱을 (d * e * ...) 현재 할당된 결과 배열의 요소와 곱한다
   (a * b) * (d * e * ...).