자바스크립트 릿코드 #4 Product of Array Except Self

들어가며

이 포스팅에서는 leetcode 추천 문제 top 75를 자바스크립트로 풀어보며 자바스크립트 공부와 알고리즘 공부를 동시에 합니다. 문제와 풀이를 적을 건데, 틀린 부분이나 더욱 개선될 부분이 있다면 댓글로 달아주시면 정말 감사하겠습니다.

문제

Product of Array Except Self

문제 설명

문제 개요

이 문제는 배열의 각 인덱스에서 자신을 제외한 나머지 숫자들의 곱을 넣어주는 문제입니다.

예제

입력: [1, 2, 3, 4]
출력: [24, 12, 8, 6]

입력: [1, 0]
출력: [0, 1]

풀이 과정

일단 처음에는 O(n^2)의 복잡도를 가진 답을 떠올렸는데, 그냥 무작정 해당 인덱스 말고 나머지를 다 곱하는 거였습니다.

대략적으로 작성한 답변은

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    return nums.map((num, index) => {
        return nums.slice(0, index).concat(nums.slice(index+1, nums.length)).reduce((acc, curV) => acc * curV);
    })
};

이러했습니다. 코드는 매우 짧았지만, 내부 함수들의 복잡도를 생각하면 매우 무거운 오퍼레이션들이 많습니다.

그 이후에 릿코드 자체에서 제공하는 솔루션을 보고 구현했는데

O(n)에 구현하는 방법이 있었습니다.

이 방법의 특징은 왼쪽의 첫번째 인덱스부터 시작하여 모든 숫자를 차례로 곱해나가는 왼쪽부터의 누적곱 배열과 오른쪽의 첫번째 인덱스부터 시작하여 모든 숫자를 차례로 곱해나가는 오른쪽부터의 누적곱 배열을 이용하는 방법이었습니다.

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    let leftProductArr = [];
    let rightProductArr = [];
    
    for(let i=0; i<nums.length - 1; i++){
        if(leftProductArr.length === 0){
          leftProductArr.push(nums[0]);  
        }else{
            leftProductArr.push(leftProductArr[i-1] * nums[i]);
        }
        
        if(rightProductArr.length === 0){
            rightProductArr.push(nums[nums.length-1]);
        }else {
            rightProductArr.push(rightProductArr[i-1] * nums[nums.length-1-i]);
        }
    }
    
    let ls = -1;
    let rs = rightProductArr.length - 1;
    
    return nums.map((num) => {
        let res = 0
        
        if(ls >= 0 && rs >= 0){
            res = leftProductArr[ls] * rightProductArr[rs];
        }else if(ls >= 0 && rs < 0){
            res = leftProductArr[ls];
        }else if(rs >= 0 && ls < 0){
            res = rightProductArr[rs];
        }
        
        ls++;
        rs--;
        
        return res;
    })
};

0에 대한 처리를 제법 길게 하다보니 이렇게 소스가 길어졌습니다. 하지만 내용은 별 거 없습니다.

사실 위 방법의 문제점은 공간복잡도를 3n이나 잡아먹는다는 것입니다. 그래서 위의 방법을 개선하면

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
	let answer = Array(nums.length).fill(1);
	
	for(let i=1; i<nums.length; i++){
		answer[i] = nums[i-1] * answer[i-1];
    }

	let right = 1;

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

	return answer;
};

이렇게 따로 Left, Right 배열을 만들지 않고 Answer 배열만으로 가능합니다.

추가적으로 숫자의 곱은 Log를 씌우면 +와 같다는 특성을 이용하여, 모든 숫자에 Log를 씌워서 더한 합을 구해놓고 해당하는 인덱스의 로그를 취한 숫자를 빼자는 의견도 있었습니다만, 0을 처리하기 까다롭습니다.

배운 점

그때그때 계산하지 않고, 미리 값을 계산해놓는다(pre-caculated)는 것은 때때로 아주 큰 도움이 됩니다. 특히 숫자 계산의 경우 여러가지 법칙들이 있습니다. 이를테면 모든 숫자의 곱이나 합은 순서가 뒤죽박죽이어도 같은 결과를 내게 됩니다. 이러한 법칙을 잘 이용합시다.

이번 경우에는 위의 법칙을 이용하여 왼쪽의 누적곱, 오른쪽의 누적곱을 미리 구해서 멋진 답을 만들어낼 수 있었습니다.