[LeetCode] Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=leetcode-75

 

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:

Input: nums = [1,2,3,4]

Output: [24,12,8,6]

Example 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.

 

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

 

 

여러개의 정수를 가진 배열이 있고, 스스로를 제외한 나머지 요소를 곱한 값으로 이루어진 배열을 리턴해야 하는 문제였다.

제한조건이라고 하면 나눗셈 기호를 사용하지 않고 문제를 풀어야 한다는 점이었다.

 

문제 풀이

평소에 reduce를 많이 써 보지 않아서 이번에는 가능한 reduce를 써서 문제를 풀어 보고 싶었다.

 

const productExceptSelf = function (nums) {
  return nums.map((num, i) =>
    nums.reduce((accumulator, currentValue, currentIndex) => {
      if (i !== currentIndex) {
        return accumulator * currentValue;
      } else {
        return accumulator * 1;
      }
    }, 1)
  );
};

 

답은 무난하게 구했는데... 엄청나게 긴 배열에 대해서는 또 효율이 떨어지는 방식이었다ㅜㅋㅋㅋ

그래서 runtime exceeded가 뜨면서 응답이 제출되지 않았음.

 

주어진 힌트를 보고 기존에 곱했던 값들을 캐싱하는 걸 고려해 보라고 하길래 

나름대로 고민을 해서 최대한 배열을...아래처럼 n*n만큼이 아니라 n*n-1만큼 돌도록 개선을 했는데...

 

function productExceptSelf(nums) {
  let nextFirst = 1;
  let result = 1;
  const resultArray = [];
  for (let i = 0; i < nums.length; i++) {
    result = nextFirst;
    for (let j = i; j < nums.length; j++) {
      if (i === j) {
        nextFirst = nextFirst * nums[j];
      } else {
        result = result * nums[j];
      }
    }
    resultArray.push(result);
  }
  return resultArray;
}

 

매번 바깥쪽 for문을 한 번 돌 때마다 기존 i까지 곱한 값을 저장하도록 하고

거기서부터 시작해서 곱셈하는 과정을 줄여 봤는데... 크게 개선이 되진 않더라ㅎ 여전히 통과 안됨.

 

그리고 결국 솔루션 보고 힌트를 얻은 다음 다시 코드를 짰다^_ㅠ

 

function productExceptSelf(nums) {
  const resultArray = Array(nums.length).fill(1);

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

  let rightNum = 1;
  for (let j = nums.length - 1; j >= 0; j--) {
    resultArray[j] = resultArray[j] * rightNum;
    rightNum = rightNum * nums[j];
  }

  return resultArray;
}

 

모든 요소가 1인 배열을 하나 만든 다음,

주어진 배열의 왼쪽부터 쭉 포인터를 이동하면서 자기 자신인 i 에서만 제외하고 배열의 요소들을 각각 곱해주고...

오른쪽에서 시작해서 한 번 더 그렇게 진행해 준다... 그럼 아래처럼 진행이 됨.

 

 

이렇게 하면 그냥 2n번만 루프를 돌면 된다... 기존에 곱해졌던 값들에 대한 캐싱도 다 되고...

언제나 그렇지만 솔루션을 볼 때마다 어떻게 이런 생각들을 하는거지? 싶다ㅋㅋㅋ

이렇게 포인터를 각각 분리해서 두 번 돌리는 것도 방법이라는 걸 깨달았다.

 

 

참고한 솔루션 링크

https://leetcode.com/problems/product-of-array-except-self/solutions/5833007/video-looping-the-input-array-twice