#238. Product of Array Except Self

문제

숫자 배열 nums를 받아서 각 요소가 본인을 제외한 다른 요소 들의 곱으로 배열을 만들어 반환하는 문제이다.

EX) A,B,C,D를 숫자라고 생각하면 [A, B, C, D]의 결과는 [BCD, ACD, ABD, ABC]이다.

제약조건: O(n)

설명

우선 for문을 중복으로 돌면 해결될 것 같지만, O(n)으로 만들어야 되기 때문에 다른 방법을 생각해보자.

위에 문제에 설명 한 것 처럼 [A, B, C, D]가 주어지면 본인의 요소를 제외한 [BCD, ACD, ABD, ABC]를 반환해야 되는데. 중복 for문이 아닌 두개의 for문으로도 해결 할 수있다.

변수 선언

변수는 왼쪽에서 부터 도는 for문을 위한 left 오른쪽에서 부터 도는 for문을 위한 right 최종 결과를 저장하기 위한 result를 선언한다.

왼쪽에서 부터 도는 for문

배열의 왼쪽부터 돌면서 첫 요소는 1을 저장하고, 그 다음 요소 부터는 이전 요소의 값을 곱해준다. [1, A, AB, ABC]

오른쪽에서 부터 도는 for문

배열의 오른쪽 부터 돌면서 [BCD, CD, D, 1] 맨 오른쪽 요소는 1을 저장하고, 그 다음 요소부터는 이전 요소의 값을 곱해준다. for문을 돌면서 left와 right를 사용해서 반환할 값을 생성한다.

답

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

var productExceptSelf = function(nums) {
  const result = [];
  const left = [];
  const right = [];

  for (let i = 0; i < nums.length; i++) {
    if (i === 0) left[i] = 1;
    else left[i] = nums[i-1] * left[i-1];
  }
  for (let i = nums.length -1; i >= 0; i--) {
    if (i === (nums.length-1)) right[i] = 1;
    else right[i] = nums[i+1] * right[i+1];
    result[i] = right[i] * left[i];
  }
  return result;
};

LeetCode

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

1
2

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

1
2

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.