LeetCode 238. Product of Array Except Self 자바 문제 풀이

문제

Product of Array Except Self - LeetCode

문제 해결 방법

• ”The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.”의 뜻은 곱셈연산시 32비트를 넘어가지 않는다는 뜻입니다. 즉, int를 사용해서 계산을 해도 괜찮습니다. 오버플로우가 일어나지 않습니다.
• 시간복잡도는 O(n)이여야 합니다.
• 나누기를 사용할수 없습니다.
• 문제 자체는 어렵지 않지만, 제약조건떄문에 어려워 지는 문제입니다. 푸는 방법은 다음과 같습니다.
  1. 자신을 제외한 왼쪽을 곱한 수를 가진 리스트를 만든다.
  2. 자신을 제외한 오른쪽을 곱한 수를 가진 리스트를 만든다.
  3. 두 자리수를 곱한다.
• 즉, 시간복잡도에 대해서 잘 알고 있고, 이를 응용할수 있는지 물어보는 문제입니다.

https://github.com/eunhanlee/LeetCode_238_ProductofArrayExceptSelf_Solution

시간복잡도: O(3n)=O(n), 공간복잡도: O(3n)

public class Solution2 {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] leftProductNums = new int[len];    // 각 요소의 왼쪽 부분 배열의 곱을 저장하기 위한 배열
        int[] rightProductNums = new int[len];   // 각 요소의 오른쪽 부분 배열의 곱을 저장하기 위한 배열
        int[] result = new int[len];         // 결과 배열

        // 각 요소의 왼쪽 부분 배열의 곱 계산
        // {1,2,3,4} -> {1,1,2,6}
        leftProductNums[0] = 1;
        for (int i = 1; i < len; i++) {
            leftProductNums[i] = nums[i - 1] * leftProductNums[i - 1];
        }

        // 각 요소의 오른쪽 부분 배열의 곱 계산
        // {1,2,3,4} -> {24,12,4,1}
        rightProductNums[len - 1] = 1;
        for (int i = len - 2; i > -1; i--) {
            rightProductNums[i] = nums[i + 1] * rightProductNums[i + 1];
        }

        // 최종 결과 배열 계산
        // {1,1,2,6} * {24,12,4,1} = {24,12,8,6}
        for (int i = 0; i < len; i++) {
            result[i] = leftProductNums[i] * rightProductNums[i];
        }

        return result;
    }
}

Follow up

공간 복잡도를 리턴할 어레이를 제외하고 O(1)만 사용해서 풀라는 추가 문제입니다. 최적화를 잘 할수 있느냐고 묻는 문제입니다.

• result 어레이에 각 요소의 왼쪽 부분 배열의 곱을 저장에 놓습니다.
• result 를 루프하며, 각 요소의 오른쪽 부분 배열의 곱을 바로 곱하여, 결과값을 넣습니다.

시간복잡도: O(3n)=O(n), 공간복잡도: O(1) without return array

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

        result[0] = 1;  // 첫 번째 요소의 왼쪽 부분 배열의 곱은 1로 초기화
        for (int i = 1; i < len; i++) {
            result[i] = nums[i - 1] * result[i - 1];  // 왼쪽 부분 배열의 곱 계산
        }

        int rightProduct = 1;  // 오른쪽에서 왼쪽으로 갈 때의 누적 곱 변수 초기화
        for (int i = len - 1; i >= 0; i--) {
            result[i] *= rightProduct;  // 왼쪽 부분 배열의 곱과 오른쪽 부분 배열의 곱을 곱하여 결과 계산
            rightProduct *= nums[i];  // 오른쪽 요소를 누적 곱 변수에 곱하여 갱신
        }

        return result;  // 결과 배열 반환
    }
}