[Prefix Sum(Product)] 238. Product of Array Except Self

문제 바로가기

 

배열이 주어졌을 때 본인(nums[i])을 제외한 나머지 원소들의 곱을 구하는 문제입니다. 배열 원소를 모두 곱하고 각 자리에 있는 애로 나누면 되겠다 싶었는데 그러지 말랍니다. 문제에서 요구하는 접근법이 따로 있나 봅니다.

 

 

Java

class Solution {
  public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];

    // prefix
    int prefixProduct = 1;
    for (int i = 0; i < n; i++) {
      answer[i] = prefixProduct;
      prefixProduct *= nums[i];
    }

    // suffix
    int suffixProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
      answer[i] *= suffixProduct;
      suffixProduct *= nums[i];
    }

    return answer;
  }
}

 

 

Kotlin

class Solution {
  fun productExceptSelf(nums: IntArray): IntArray {
    var answer = IntArray(nums.size)

    var prefixProduct = 1
    for (i in 0 until nums.size) {
      answer[i] = prefixProduct
      prefixProduct *= nums[i]
    }

    // println(answer.contentToString()) // 배열 출력

    var suffixProduct = 1
    for (i in nums.size - 1 downTo 0) {
      answer[i] *= suffixProduct
      suffixProduct *= nums[i]
    }

    return answer
  }
}

 

 

구간합(Prefix Sum) 의 개념을 써먹었습니다. 먼저 구간 곱을 앞에서부터(Prefix Product) 를 해봅시다. 

nums = [1, 2, 3, 4]
prefixProduct = [1, 1, 2, 6]

 

본인(nums[i]) 은 곱하면 안되기에 구간 곱을 수행하면 위와 같이 나옵니다. prefixProduct[i] = product(nums[0]~nums[i-1]) 이 되는거죵.

이렇게 하면 prefixProduct[i] 에는 nums[k] (i < k < nums.length) 들이 곱해져있지 않습니다. 그래서 이제 뒤에서도(Suffix Product) 곱해주면 됩니다. 

 

nums = [1, 2, 3, 4]
prefixProduct = [1, 1, 2, 6]
suffixProduct = [24, 12, 4, 1]
----------------------------------------
answer = [24, 12, 8, 6] (prefixProduct x suffixProduct)

 

마찬가지로 suffixProduct[i] 는 nums[nums.length - 1] ~ nums[i + 1]의 곱과 같습니다. 그리고 suffixProduct[i] 에는 i 보다 작은 인덱스의 원소들은 곱해져있지 않죠. 그럼 prefixProduct 의 결과와 suffixProduct 의 결과를 곱하면 최종적으로 우리가 원하는 답이 나옵니다.~~~

 

 

 

 

감사합니다!!!