[문제11][LeetCode] 238. 자신을 제외한 배열의 곱

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

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].
정수 배열 nums가 주어졌을 때, answer[i]가 nums[i]를 제외한 nums의 모든 요소의 곱과 같게 하는 배열 answer를 반환해주세요.

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
nums의 어떤 접두사나 접미사의 곱은 32비트 정수 안에 들어갈 것이 보장됩니다.

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

O(n) 시간에 실행되고 나눗셈 연산을 사용하지 않는 알고리즘을 작성해야 합니다.

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.

 

접근 방법

O(n) 시간에 실행되고 나눗셈 연산을 사용하지 않는 알고리즘을 사용해야 한다.

그럼 left, right배열을 만든 후 left[i], right[i]에는   nums[i]의 왼쪽 전체, 오른쪽 전체 값을 곱한 숫자를 저장한다. 최종적으로 answer[i]는 left[i] *right[i] 리턴

 

코드 구현

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

        int[] left = new int[n];
        int[] right = new int[n];

        left[0] = 1;
        right[n - 1] = 1;

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

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

        for (int i = 0; i < n; i++) {
            answer[i] = left[i] * right[i];
        }

        return answer;
    }
}