Leetcode 238. Product of Array Except Self

238. Product of Array Except Self

오늘은 릿코드 238번문제입니다. 난이도 - 중

 

문제설명

 

Medium

 

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.

---

이번문제는 파라미터로 nums 배열이 들어왔을 때 해당 인덱스를 제외한 모든 나머지 인덱스 값을 곱한 값을 해당 인덱스로 가지는 배열을 리턴하는 함수를 구현하는 것입니다.

 

예제 1번을 보면

아웃풋 배열의 첫번째 24는 nums에서 0번째 인덱스(1)을 제외한 2, 3, 4 모두 곱한 값 입니다.

마찬가지로 두번째 12는 nums에서 1번째 인덱스(2)를 제외한 1, 3, 4 모두 곱한 값 입니다.

이렇게 해당 인덱스를 제외한 모든 나머지 인덱스의 값들을 곱한 값을 해당 인덱스로 가지는 배열을 리턴하는 것입니다.

 

그럼 문제를 풀어보겠습니다.

---

문제풀이

Brute-force

먼저 예제 1을 기준으로 순서대로 생각해보면

arr[0]=nums[1]*nums[2]*nums[3];
arr[1]=nums[0]*nums[2]*nums[3];
arr[2]=nums[0]*nums[1]*nums[3];
arr[3]=nums[0]*nums[1]*nums[2];

을 값으로 가지는 배열을 리턴해 주면 됩니다.

이렇게 구현을 하기 위해서는 for loop 를 두번 돌리면 될 것입니다.

 

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    //brute-force approach
    const arr = [];
    let product = 1;
    for (let i=0; i<nums.length; i++) {
        for (let j=0; j<nums.length; j++) {
            if (i==j)
                continue;
            product *= nums[j]; 
        }
        arr.push(product);
        product = 1;
    }
    return arr;
};

arr 배열을 선언해주고

곱셈 기준값을 1로 잡은 다음

인덱스가 같을 경우 (i==j), 곱셈 연산을 건너뛰고 나머지는 모두 product로부터 곱해줍니다.

내부 for loop 가 끝나면 product 값을 arr 에 붙여준 후 product 값을 1로 다시 초기화 해 줍니다.

 

brute-force 성능

성능은 좋지 않은 것으로 보입니다.

좀 더 나은 방법으로 접근해 보겠습니다.

prefix, postfix 이용

prefix 와 postfix 를 이용해서 풀어보겠습니다.

이 접근 방법은 해당 배열의 인덱스 전값을 모두 곱한 값을 prefix 에 저장시키면서 return 될 array(result)에 넣어준 다음, 다시 마지막 전의 인덱스부터 거꾸로 돌아오면서 해당 배열 인덱스 후값을 모두 곱한 값을 postfix 에 저장시키면서 result array의 값들을 다시 업데이트 해주는 방법입니다.

일단 코드부터 보겠습니다.

 

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const result = [];
    let prefix = 1;
    let postfix = 1;
    
    for (let i = 0; i < nums.length; i++) {
        result[i] = prefix;
        prefix *= nums[i];
    }
    for (let i = nums.length - 2; i >= 0; i--) {
        postfix *= nums[i + 1];
        result[i] *= postfix;
    }
    
    return result;
};

일단 결과로 리턴될 result 배열을 생성하고 prefix, postfix 값으로 1을 할당해줍니다.

첫 for loop 에서는 해당배열 인덱스 전값을 순차적으로 더해줍니다.

• 첫번째 for loop
  
  • result[0] = 1, prefix = 1
  • result[1] = 1, prefix = 2
  • result[2] = 2, prefix = 6
  • result[3] = 6, prefix = 24

이렇게 해서 result 배열이 다음과 같아졌습니다.

result = [1, 1, 2, 6]

해당 값을 살펴보게 되면 prefix 가 해당 인덱스의 전 인덱스를 모두 곱한 값이 됩니다.

인풋이었던 [1, 2, 3, 4] 와 비교해 보면 쉽게 알 수 있습니다.

마지막 result 값은 전값을 모두 곱한 값이므로 두번째 for loop 에서 제외합니다.

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

두번째 루프에서는 인덱스 후의 값들을 모두 곱한 값을 result[i] 에 곱하여 넣어줍니다.

표로 전체 코드 변화를 한번 살펴보겠습니다.

nums = [1, 2, 3, 4] 

i	num[i]	prefix	result[i]	postfix
0	1	1	[1]	1
1	2	2	[1, 1]	1
2	3	6	[1, 1, 2]	1
3	4	24	[1, 1, 2, 6]	1
2	3	24	[1, 1, 8, 6]	4
1	2	24	[1, 12, 8, 6]	12
0	1	24	[24, 12, 8, 6]	24

 

이렇게 해서 결과값인 [24, 12, 8, 6]을 얻을 수 있습니다.

결국 곱한 값은 해당인덱스의 전 값을 모두 곱한 값 * 해당인덱스 후 값을 모두 곱한 값 이 되므로 loop를 처음부터 한번 돌고 마지막 전부터 처음까지 한번 또 돌면 result 배열이 완성이 되고 리턴해 주면 됩니다.

prefix, postfix 성능

 

런타임이 훨씬 좋아졌습니다.

 

---

 

이상으로 238번 문제 Product of Array Except Self를 마치겠습니다.

※ 앞으로 모든 문제를 JavaScript 로 올릴 예정입니다.

다른 문제 풀이도 깃헙에서 확인 할 수 있습니다.