[75 LeetCode] 21 - Product of Array Except Self

[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.

블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

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

Product of Array Except Self - LeetCode

 

쉬운 문제다. 

1) 내가 생각한 방법

전체 곱을 구해놓고 리스트를 순회하며 전체 곱에서 현재 숫자를 나눠준다.

두 번 순회만으로 끝낼 수 있다.

이 때, 0이 있는 경우에 예외 케이스가 생길 수 있으므로 해당 경우에 대해 체크해준다.

처음엔 reduce, map으로 짰는데 속도가 안나와서 일반 for문으로 바꿔줬다.

var productExceptSelf = function(nums) {
    let zeroCount = 0;
    let allProduct = 1;

    for (let i = 0; i < nums.length; i++) {
        if (!nums[i]) {
            zeroCount += 1;
            continue;
        }
        allProduct *= nums[i];
    }

	// 0이 두개 이상이면 모든 경우 0이 곱해지기 때문에 0으로 찬 배열을 리턴
    if (zeroCount > 1) return nums.fill(0);

    for (let i = 0; i < nums.length; i++) {
        if (!nums[i]) {
        	// 0이 하나인 경우 현재 num이 0일때는 모든 수의 곱을 반환
            nums[i] = allProduct;
            continue;
        }
		
        // zeroCount가 1이면
        // 0이외에는 모두 0을 반환
        // 그렇지 않은 경우 곱에서 현재 수를 뺀 결과를 반환
        nums[i] = zeroCount ? 0 : allProduct / nums[i];
    }

    return nums;
};

솔루션에는 다음과 같은 알고리즘을 제시하고 있었다.
왼쪽에서부터 하나씩 곱하고, 오른쪽에서부터 하나씩 곱해준다.

left, right가 누적되면서 곱해지기 때문에 자기 위치에 왔을 때
left값 = 현재 숫자 전까지의 곱
right값 = 현재 숫자 이후의 곱

이므로 그 둘을 곱하면 자신 빼고 나머지에 대한 곱이 된다.
근데 곱셈연산이 3n회 발생하기 때문에 이게 더 느릴 것 같았는데 결과는 비슷했다.

위에 작성한 방식은 곱셈 n회 나눗셈 n회이지만 아무래도 나눗셈이 더 느린 연산이라 그런 것 같다.

var productExceptSelf = function(nums) {
  const n = nums.length;
  const result = new Array(n).fill(1);


  // 왼쪽부터 곱을 쌓아가며 result에 곱한다.
  let left = 1;
  for (let i = 0; i < n; i++) {
    result[i] = left;
    left *= nums[i];
  }
  
  // 오른쪽부터 곱을 쌓아가며 result에 곱한다.
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= right;
    right *= nums[i];
  }


  return result;
}