238. Product of Array Except Self

Top interview의 medium 난이도 문제

 

두가지 풀이로 풀어본 문제

자기 자신을 제외한 모든 원소들의 곱을 구하는 문제

이때 매번 곱의 결과를 구할 경우 O(n^2) 만큼 걸리기 때문에, 

 

첫번째 풀이는

매번 구할 경우 O(n^2) 만큼 걸리기 때문에, 왼쪽에서부터의 누적곱과 오른쪽에서의 누적곱 배열을 각각 만들어서

정답 배열에 넣는 방식으로 풀었다.

배열이 3개 필요하다.

public static int[] productExceptSelf(int[] nums) {
        int size = nums.length;
        int[] left = new int[size];
        int[] right = new int[size];
        int[] answer = new int[size];

        left[0] = nums[0];
        right[size - 1] = nums[size - 1];

        for (int i = 1; i <= size - 1; i++) {
            left[i] = left[i - 1] * nums[i];
            right[size - 1 - i] = right[size - i] * nums[size - 1 - i];
        }
        for (int i = 0; i < size; i++) {
            if (i == 0) {
                answer[i] = right[1];
            } else if (i == size - 1) {
                answer[i] = left[size - 2];
            } else {
                answer[i] = left[i - 1] * right[i + 1];
            }
        }
        return answer;
    }

 

두번째 풀이

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

공간복잡도 O(1)로만 문제를 풀었다.

 

left, right 배열을 사용하지 않고, ans(answer) 배열만 사용한다.

1. 먼저 ans 배열에 왼쪽부터의 곱을 넣고

2. 오른쪽에서부터는 right 변수(배열 아님)에 오른쪽에서부터의 곱을 누적해 오면서, 그 값을 기존에 구해둔 left 곱을 넣어둔 ans와 곱해준다.

여기서 조금 난해했던 부분이, right 변수를 사용하지 않고 ans 배열만 사용해서 계산할 경우, ans 배열에서 왼쪽에서부터 구한 값과, 오른쪽에서 구한 값이 섞이면서 오른쪽에서부터의 곱을 제대로 들고있지 못해서 올바른 값을 도출할 수 없다. 따라서 반드시 right 변수에 오른쪽에서부터의 곱을 누적해서 별도로 들고있어야 한다.

public static int[] productExceptSelf(int[] nums) {
        int size = nums.length;
        int[] ans = new int[size];

        ans[0] = 1;
        for (int i = 1; i <= size - 1; i++) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        int right = 1;
        for (int i = size - 1; i >= 0; i--) {
            ans[i] *= right;
            right *= nums[i];
        }

        return ans;
    }