[알고리즘] LeetCode_#238

238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

✨ Example

Input: nums = [0, 4, 0]
Output: [0, 0, 0]

🚨 Constraints

▶︎ 풀이

int배열 nums 를 순차 탐색하면서 현재 인덱스의 값 nums[i] 를 제외한 나머지 요소들의 곱을 i번째 요소로 한 int배열 answer를 출력하는 문제

👉 나의 생각
answer[i]의 값은 전체 nums의 요소의 곱 / nums[i] 의 값과 같다.
단, nums[i]의 값이 0일 경우 divided by zero 오류가 발생하므로 해당 케이스의 처리가 필요

▶︎ 기존코드

❌ 오답 : 0에 대한 처리 누락

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int ans[] = new int[n];
        int pro = 1;
        for(int i : nums) {
            pro *= i;
        }
        
        for(int i = 0; i < n; i++) {
            ans[i] = pro / nums[i];
        }
        return ans;
    }
}

💡 힌트1: 각 인덱스에 대해 self를 제외한 모든 요소의 곱을 계산하기 위해 prefix와 suffix의 곱을 효율적으로 활용할 수 있는 방법을 생각해보자.
💡 힌트2: 메모리를 재사용하거나 중간 결과 저장을 위한 입력 배열을 수정하면 추가적인 공간 사용량을 최소화 할 수 있습니다.

▶︎ 개선사항

Solutions를 참고하여 문제 풀이 확인

1. 힌트 1 적용
   prefix의 값을 저장할 배열 pre[]와
   suffix의 값을 저장할 배열 suff[]를 선언하고
   루프 내부에서 pre[i]는 앞 인덱스를 곱한 값 nums[i-1], suff[i]는 뒤 인덱스를 곱한 값 nums[i+1]를 저장한다.
   그리고 결과값인 배열 ans[i] 에는 pre[i]*suff[i]를 계산하여 저장한다.
2. 힌트 2 적용
   프로그램의 공간 복잡도를 최적화
   별도의 배열 pre[]와 suff[] 를 선언하지 않고 결과값을 직접 ans[]에 저장
   

▶︎ 수정코드

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int ans[] = new int[n];
        Arrays.fill(ans, 1);
        int curr = 1;
        for(int i = 0; i < n; i++) {
            ans[i] *= curr;
            curr *= nums[i];
        }
        curr = 1;
        for(int i = n - 1; i >= 0; i--) {
            ans[i] *= curr;
            curr *= nums[i];
        }
        return ans;
    }
}

---

💭 Solutions의 풀이를 직접 풀어볼 것!