176일 (CodeTestcaseTestcaseTest Result238. Product of Array Except Self) Array

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 <= 10^5
• -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.)

 

 

 

- 접근방법

 

0. example1를 보면 간단하다.

모든 원소들의 곱은 24, 그리고 각각의 nums[i] 자기자신으로 나눈 값을 answer[i]에 붙여넣으면 끝이다.

하지만 nums에 0이 없거나, 혹은 0이 1개 존재하거나, 2개이상 존재할 때마다 다른 방식으로 접근이 필요하다.

 

 

1. nums에 0이 2개 이상 존재할 때(zeros[0] >= 2)

→ 자기자신을 제외한 모든 수의 곱에 0을 무조건 곱해지게 되므로 answer의 모든 원소는 0이 된다.

따라서 기본값으로 초기화 된 배열을 리턴한다.

 

 

2. nums에 0이 2개 이상 존재할 때(zeros[0] == 1)

→ 현재 자신이 0일 경우 자기자신을 제외한 모든 수의 곱은 0이 아니다.

= nums[i] == 0 인 경우 자기자신을 제외한 모든 수의 곱을 answer[i]에 붙여넣는다.

 

→현재 자신이 0이 아닌 수는 자기자신을 제외한 모든 수의 곱이 0이다.
answer의 초기값은 0이므로 따로 연산은 하지 않는다.

 

 

3. nums에 0이 존재하지 않을 때(zeros[0] == 0)

→ 접근방법 0번과 같다.

모든 원소들의 곱(product)를 각각의 nums[i] 자기자신으로 나누고 answer[i]에 붙여넣으면 끝이다.

 

 

- 추가

zeros[1] 을 추가적으로 사용한 이유는

zeros[0] == 1인 경우 0의 위치를 찾기위해 불필요한 추가 연산을 막기 위함이다.

 

 

- 코드

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


        for(int i = 0; i < n; i++) { // 0~3
            if(nums[i] == 0) {
                zeros[0]++;
                zeros[1] = i; // zeros[0] == 1일때 를 위해 인덱스를 기억
            }
            else product *= nums[i];
        }

        if(zeros[0] >= 2) return new int[n]; // 1
        else if(zeros[0] == 1) { // 2
            answer[zeros[1]] = product;
            return answer;
        }
        else { // 3
            for(int i = 0; i < n; i++) {
                answer[i] = product / nums[i];
            }
            return answer;
        }

    }
}

 

일일문제라서 풀었지만 퀴즈같아서 재미있게 풀었다.

제출을 위한 공간을 제외한 추가공간도 O(1)로 해결할 수 있었다.

 

배열 zeros[0]은 0의 개수를 카운트하기 위함이지만, zeros[1]은 nums[i]가 0인 인덱스 i를 기억하기 위함인데
변수명을 어떻게 정해야할지 생각해봐야겠다.

 

 

 

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