[LeetCode] 238. Product of Array Except Self - Java

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

Product of Array Except Self - LeetCode

---

문제

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 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

 

Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

 

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.)

---

풀이

풀이 과정

주어진 배열에서 각 인덱스마다 자기 자신을 제외한 원소들의 곱셈 결과를 구하는 문제이다.
각 인덱스마다 왼쪽 원소들의 곱과 오른쪽 원소들의 곱을 구해 두 값을 곱하는 방식으로 풀이한다.

먼저 return할 결과값 배열을 선언하고

int[] result = new int[nums.length]; // return할 결과값 배열

 

nums 배열을 왼쪽 부터 탐색하며 i번째 인덱스에 i - 1번째 인덱스의 값을 계속 곱해가며 인덱스 왼쪽에 있는 값들의 곱을 구한다

int multiple = 1; // 초기값
for(int i = 0; i < nums.length; i++) { // 왼쪽 수의 곱
    result[i] = multiple;   // result배열 i번째 값에 곱셈 결과를 넣고
    multiple *= nums[i];    // 곱셈 결과값을 증가시킴
};

반대로 오른쪽부터 탐색하며 i번째 인덱스에 i + 1번째 인덱스의 값을 계속 곱해나가면 인덱스 오른쪽에 있는 값들의 곱을 구할 수 있는데, 인덱스 마다 왼쪽에 있는 값들의 곱을 구해놓았으므로 이 값과 곱하면 해당 인덱스에 있는 값을 제외한 나머지 수들의 곱을 구할 수 있다.

multiple = 1;
for(int i = nums.length - 1; i >= 0; i--) { // 오른쪽 수의 곱
    result[i] *= multiple;  // result배열 i번째 값에 현재 값과 곰셈 결과를 곱한 값을 넣고
    multiple *= nums[i];    // 곱셈 결과값을 증가시킴
}

return result; // 결과값을 반환

---

최종 코드

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length]; // return할 결과값 배열
        
        int multiple = 1; // 초기값
        for(int i = 0; i < nums.length; i++) { // 왼쪽 수의 곱
            result[i] = multiple;   // result배열 i번째 값에 곱셈 결과를 넣고
            multiple *= nums[i];    // 곱셈 결과값을 증가시킴
        };
        
        multiple = 1;
        for(int i = nums.length - 1; i >= 0; i--) { // 오른쪽 수의 곱
            result[i] *= multiple;  // result배열 i번째 값에 현재 값과 곰셈 결과를 곱한 값을 넣고
            multiple *= nums[i];    // 곱셈 결과값을 증가시킴
        }
        
        return result; // 결과값을 반환
    }
}

---