LeetCode: 238번 (Product of Array Except Self) [JAVA]

문제 링크

https://leetcode.com/problems/product-of-array-except-self/

Product of Array Except Self - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 왼쪽부터 오른쪽으로 nums 배열의 값이 누적되며 곱해지는 배열과 오른쪽부터 왼쪽으로 nums 배열의 값이 누적되며 곱해지는 배열 2개를 생성 후 초기화
2. 하나의 위치 i에 대해 왼쪽부터 오른쪽 배열의 i -1 인덱스 값 * 오른쪽부터 왼쪽 배열의 i + 1 인덱스 값으로 answers 배열을 초기화

 문제에서 요구하는 제한 사항인 나누기를 사용하지 않아야 한다는 점이 좀 까다로웠던 문제이다. 문제에서 요구하는 답들이 배열 속 자기 자신을 제외한 나머지의 곱하기 값을 요구하다보니, 흔히 생각할 수 있는 해결 방법이 0을 제외한 모든 값들을 미리 곱해놓고 자기 자신에 해당하는 값들에 대해서만 나눠서 답을 채우는 과정을 생각할 수 있다. 하지만 이 방법이 불가능하기에 자기 자신을 제외한 곱을 다르게 생각해야 한다.

 이 때 적용한 해답은 배열을 자기자신을 기준으로 분할하는 방법이다. 배열을 자기자신을 기준으로 왼쪽, 오른쪽으로 분할한 다음 왼쪽의 요소들을 모두 곱한 값, 오른쪽 요소들을 모두 곱한 값을 최종적으로 곱해서 답으로 하면 된다. 이때 물론 매번 요소들을 곱하는 과정을 하면 복잡도가 n^2가 되기 때문에 이를 미리 해놓아야 하는데, 이건 애초에 왼쪽부터 오른쪽으로, 오른쪽부터 왼쪽으로 값을 저장할 배열을 만들어놓고 한 번에 누적값을 저장해놓으면 바로 사용할 수 있다.

 

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] answers = new int[nums.length], leftToRight = new int[nums.length], rightToLeft =new int[nums.length];

        //왼쪽부터 오른쪽으로 누적 곱 저장
        leftToRight[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            leftToRight[i] = nums[i] * leftToRight[i - 1];
        }

        //오른쪽부터 왼쪽으로 누적 곱 저장
        rightToLeft[nums.length - 1] = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i--) {
            rightToLeft[i] = nums[i] * rightToLeft[i + 1];
        }

        //정답 배열 초기화
        answers[0] = rightToLeft[1];
        answers[nums.length - 1] = leftToRight[nums.length - 2];
        for (int i = 1; i < nums.length - 1; i++) {
            answers[i] = leftToRight[i - 1] * rightToLeft[i + 1];
        }

        return answers;
    }
}

결과