[Leetcode] 238번 - Product of Array Except Self

1. 문제 파악

• 문제 링크: https://leetcode.com/problems/product-of-array-except-self/description/
• 문제: 자기 자신을 제외한 주어진 배열의 모든 요소의 곱셈을 저장한 배열 반환
• 시간복잡도 파악: 입력 크기가 10000개 이내라서 O(N log N)이하면 되지만, 문제에서 O(N)이내로 해결하라고 명시되어 있다.

---

2. 문제 풀이

1. 브루트 포스로 문제 풀이 도출

1. 배열을 순차적으로 조회한다.
2. 현재 조회하는 요소가 아닌 모든 요소의 곱을 반환할 배열에 저장한다.

위의 로직대로라면 O(N^2)시간이 걸린다.

 

2. 핵심 문제 풀이 도출

시간복잡도가 O(N) 내에 해결해야하므로, 배열 조회할때 반환할 배열의 연산(계산과 저장) 끝나야한다. 배열 조회 시간이 O(N)이기 때문이다.

 

브루트 포스인 첫번째 요소부터 마지막 요소까지 순차적으로 조회하면서 연산을 하는 것은 O(N^2)이 걸린다. 그렇다면 배열 조회 시간 내에 연산이 끝나야하므로 아이디어를 떠올려야한다.

 

시간 복잡도 연산이 O(N) x O(N)이 아닌 O(N) x n으로 끝날수 있는 생각을 해봤다.

 

일단, 구하고자하는 결과값은 현재 조회 요소를 제외한 요소들의 누적곱이다. 이를 배열 조회를 N번을 수행해서 연산을 마쳐야한다.

 

처음부터 끝까지 배열을 순회하는것은 시간내에 연산이 안되므로, 현재 조회한 배열 요소를 양쪽에서 조회하는 것을 생각해볼수있다.

아래와 같이 현재 지정한 요소값이 2일때 왼쪽에서 오른쪽으로 스캔을 해서 누적값을 구할수도 있지만, 양쪽 방향에서 스캔을 해서구할수도 있다. 그러면 "왼쪽에서 오른쪽으로"와 "오른쪽에서 왼쪽으로" 2번 스캔해서 누적값을 구할수있는 실마리이다.

v: 현재 지정한 요소
>: 누적 곰셈을 해야할 요소

> v > > > 
1 2 3 4 5 

> v < < <
1 2 3 4 5

 

일단, 스캔하면서 누적 곱을 저장할 결과값 배열이 필요하다. 해당 배열에 누적으로 곱해야하므로 0이 아닌 1로 초기화가 필요하다.

1. 결과값인 누적곱을 저장할 배열을 1로 초기화
2. 왼쪽에서 오른쪽으로 순회하면서 누적곱 배열 요소에 누적해서 곱한다.
3. 오른쪽에서 왼쪽으로 순회하면서 누적곱 배열 요소에 누적해서 곱한다.

 

위의 로직에 대해서 풀어서 설명하자면 다음과 같다.

1. 결과값인 누적곱을 저장할 배열을 1로 초기화
2. 왼쪽에서 오른쪽으로 스캔시, 왼쪽 스캔 누적곱 배열에 저장
3. 오른쪽에서 왼쪽으로 스캔시, 오른쪽 스캔 누적곱 배열에 저장
4. 왼쪽 스캔 누접 곱 배열과 오른쪽 스캔 누접 곱 배열을 곱합다.

1 2 3 4 // 주어진 배열
1 1 1 1 // 1. 결과값인 누적곱을 저장할 배열을 1로 초기화
1 1 2 6 // 2. 왼쪽에서 오른쪽으로 스캔시, 왼쪽 스캔 누적곱 배열에 저장
24 12 4 1 // 3. 오른쪽에서 왼쪽으로 스캔시, 오른쪽 스캔 누적곱 배열에 저장
24 12 8 6 // 4. 왼쪽 스캔 누접 곱 배열과 오른쪽 스캔 누접 곱 배열을 곱합다.

 

반환할 배열은 2번, 3번과 4번의 요소를 저장할 3개의 배열을 생성해도 되지만, 하나의 반환 배열만 생성해서 해결할수있다. 2번 연산을 한 각 배열의 요소에 3번 연산을 하면되기 때문이다. 그러면 4번의 배열 값이 나온다.

 

3. 입출력 케이스 도출 및 문제 풀이 도출 확인

• 일반 케이스
  • [1,2,3,4] -> [24,12,8,6]
  • [-1,1,0,-3,3] -> [0,0,9,0,0]
• 엣지 케이스
  • [0, 0] -> [0, 0]

위의 알고리즘대로라면 엣지 케이스까지 커버가능하다.

 

4. 코드로 문제 풀이 구현

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        // 1. 결과값인 누적곱을 저장할 배열을 1로 초기화
        for (int i = 0; i < n; i++) {
            answer[i] = 1;
        }

        // 2. 왼쪽에서 오른쪽으로 순회하면서 누적곱 배열 요소에 누적해서 곱한다.
        for (int i = 0, left = 1; i < n; i++) {
            answer[i] *= left; 
            left *= nums[i]; 
        }

        // 3. 오른쪽에서 왼쪽으로 순회하면서 누적곱 배열 요소에 누적해서 곱한다.
        for (int i = n-1, right = 1; i >= 0; i--) {
            answer[i] *= right; 
            right *= nums[i];
        }
        return answer;
    }
}

 

5. 복잡도

• 시간 복잡도
  • 왼쪽에서 오른쪽으로 배열 순회: O(N)
  • 오른쪽에서 왼쪽으로 배열 순회: O(N)
  • 최종 시간복잡도: O(N) + O(N)이므로 O(N)이다.
• 공간 복잡도
  • 추가 공간은 누적값 배열 요소를 저장하기 위해 O(N)이다.