[알고리즘] Leetcode_238_Product of Array Except Self

Problem

Solve

처음 생각했던 것은 Example 2 를 보고 nums[i]가 0일 경우의 수를 고려해보았다.
일단 시작은 모든 배열의 곱 mul 을 구한다.
1. 모든 배열 값이 0인 경우
2. 아닌 경우
2-1. 배열 값이 0이 아닌 경우에는 mul/nums[i]
2-2. 배열 값이 0인 경우에는 mul 값으로

그치만 2인 경우에 0인 요소가 몇 개인지에 따라서 또 경우의 수가 갈린다는 것이다.

제외할 수 있는 방법이 무엇이 있을까 하고
toRight, toLeft 로 각각 좌에서 우로, 우에서 좌로 요소들의 곱이 진행되는 배열들을 생성하고 할당한다.

제외할 수 있는 방법은
1. 인덱스가 양 끝인 경우
1-1. 인덱스가 0인경우는 toLeft의 인덱스 1인 경우가 자기 자신을 제외한 곱이다.
1-2. 인덱스가 마지막인경우는 toRight의 인덱스 마지막-1 인 경우가 자기 자신을 제외한 곱이다.
2. 인덱스가 양 끝 사이인 경우
자기 자신의 인덱스 전의 곱 = toRight[index-1] 과 자기 자신의 인덱스 후의 곱 = toLeft[index+1] 을 곱해준 값이 곧 자기 자신을 제외한 곱이다.

내가 풀기에는 배열을 두 개로 나누어서 결과값을 구할 때는 두 배열을 합치는 식으로 진행을 하였으나,

class Solution {
  public int[] productExceptSelf(int[] nums) {

    int result [] = new int [nums.length];

      int runningProduct = 1;

      //left Pass
      for(int i = 0; i < nums.length; i++){

          result[i] = runningProduct;//for every index we will put runningProduct
          runningProduct = runningProduct * nums[i];//update the runningProduct
      }

      //rightPass
      //for rightPass Again update runningProduct as 1

      runningProduct = 1;

      for(int i = nums.length -1 ; i >= 0; i--){

          //multiply the value present on ith index with rightPass Value

          result[i] = result[i] * runningProduct;
          runningProduct = runningProduct * nums[i];//update the runningProduct
      }
      return result;  
  }
}

이렇게 한 배열로 해결하는 과정도 있었다.
이것은 곱을 구해줄 때 자기 자신을 곱하기 전의 곱을 저장하는 방식으로 하면 나와 같은 방식인 것이다.