[Medium] 238. Product of Array Except Self (애플 코딩 테스트 문제)

Leetcode 238번 문제는 정수로 채워진 array가 주어지고, 원래의 index에있는 값을 제외한 모든 index의 값을 곱한 값이 들어있는 array를 return하는 문제이다. 

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int product = 1;
        for(int i = 0; i < nums.length;i++){
            product *= nums[i];
        }
        int[] arr = new int[nums.length];
        
        for(int i = 0; i < nums.length;i++){
            if(nums[i] == 0){
            arr[i] = product;
            }
            else{
                 arr[i] = product / nums[i];
            }
        }
        return arr;   
    }
}

모든 값을 곱한 값에 array를 loop through하면서 원래의 값으로 나누면 되겠지만 이건 문제에도 나와있듯이 나누기는 금지돼있기 때문에 정답으로 쓸 수 없다.

class Solution {
    public int[] productExceptSelf(int[] nums) {
    int[] answer = new int[nums.length];
    for(int i = 0; i < nums.length;i++){
    int product = 1;
    }
    for(int j = 0; j < nums.length; j++){
    if(i!=j){
    product *= nums[j];
          }
        }
    answer[i] = product;
      }
    return answer;
    }
  }

위 풀이는 brute-force를 사용한 풀이인데 time complexity가 O(n)이 돼야 하기 때문에 이 풀이 역시 사용할 수 없다. 

 

#풀이

class Solution {
    public int[] productExceptSelf(int[] nums) {
      int[] left = new int[nums.length];
      int[] right = new int[nums.length];
      int[] answer = new int[nums.length];
     
        left[0] = 1;
        right[nums.length - 1]= 1;
        for(int i = 1; i < nums.length; i++){
            left[i] = nums[i-1] * left[i - 1];
            right[right.length -1 - i] = nums[nums.length - i] * right[right.length -i];
        }
        
        for(int i = 0; i < nums.length; i++){
            answer[i] = left[i] * right[i];
        }
        return answer;   
}
}

이 풀이는 left array와 right array를 만들어 left array의 맨 왼쪽을 1로 만들고, right array의 맨 오른쪽도 1로 만들고 시작한다. left array는 i  = 1에서 시작하고 nums array에 nums[i] 와 nums[i-1] 곱한 값으로 채워나간다. right array도 마찬가지로 nums.length - 1 에서 시작하고 1씩 index를 줄여나간다. 예를 들어 [1, 2, 3,4] 라는 array가있으면 left array는 [1, 1, 2, 6] (마지막 4는 제외) 이 되고,  right array는 [24, 12, 4, 1]  (첫번째 1 제외)이 된다. 마지막으로 left array와 right array를 상응하는 index끼리 곱해주면 [24, 12, 8, 6] 의 정답 array가 된다. 이 알고리즘의 time complexity는 O(2n) 이다.

# O(1) Space Complexity풀이

class Solution {
    public int[] productExceptSelf(int[] nums) {
    int[] answer = new int[nums.length];
        
    answer[0] = 1;
        for(int i=1; i < nums.length;i++){
            answer[i] = answer[i-1] * nums[i-1];
        }
        int right = 1;
        for(int i = nums.length - 1; i >= 0; i--){
            answer[i] *= right;
            right *= nums[i];
        }
        return answer;
}
}

위 풀이는 첫 번째 풀이와 똑같은 로직 이지만 array를 하나만 사용한 풀이이다. answer array하나만 사용하기 때문에 space complextiy가 O(1)이다. 문제에도 나왔듯이 output array는 extra memory로 치지 않는다.