238. Product of Array Except Self

 

📌 문제 링크 :

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

 

✅ 내 풀이(Success) :

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

        for (int i = 1; i < n; i++) {
            answer[i] *= nums[i-1] * answer[i-1];
        }

        for (int i = n-2; i >= 0; i--) {
            answer[i] *= nums[i+1];
            nums[i] *= nums[i+1];
        }

        return answer;
    }
}

 

🧐 리뷰 :

어떻게 문제를 해결해야 할지 아이디어가 떠오르지 않아 고민 끝에 토론 탭의 답변들을 참고했지만, 내용이 잘 이해되지 않았다.

그래도 연습장에서 시간 복잡도를 O(N)으로 구현하기 위해 중첩 반복문 대신 단일 반복문을 두 번 나누어 계산하는 방법으로 접근했고, 여러 번의 시도 끝에 방법을 찾아 생각한 내용을 그대로 코드로 옮기니 문제를 해결할 수 있었다.

문제를 푼 후 다른 사람들의 풀이를 확인해보니 나와 비슷한 방식으로 구현했지만, 곱셈 연산을 왼쪽 방향과 오른쪽 방향으로 진행할 때 사용한 변수 정의 방식이 달랐다.

변수를 명확하게 정의한 코드가 내 코드보다 조금 더 직관적이어서 이해하기 쉬운 풀이처럼 느껴졌다.

 

🏷️ 참고 자료:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] output = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            output[i] = 1;
        }

        int left = 1;
        for (int i = 0; i < nums.length; i++) {
            output[i] *= left;
            left *= nums[i];
        }

        int right = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            output[i] *= right;
            right *= nums[i];
        }

        return output;        
    }
}