[leetcode] 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.

 

examples.

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

 

풀이 🚀

 

처음엔 이중 포문을 사용해서 i != j인 경우에만 곱해서 배열에 삽입해주었다.

하지만 시간 초과 발생!!

따라서 모든 수를 모두 곱한 다음, 0의 개수에 따라서 구분하는 방식을 취했다.

즉, 먼저 nums를 순회하면서 모든 값을 다 곱해둔다. (product)

대신 0인 경우에는 곱하지 않고 zeroCount를 하나 올려준다.

 

만약 zeroCount > 1인 경우에는 자기 자신을 제외하더라도 0이 무조건 존재한다는 의미이기에 모두 0인 배열을 반환한다.

그렇지 않은 경우에는 다시 nums를 순회하면서, zeroCount == 1인 경우에는 내가 0인지, 남이 0인지 판단하여 계산한다.

 

 

소스코드 👩🏻‍💻

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int zeros = 0;
        int product = 1;
        int[] answer = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                zeros++;
                continue;
            }
            product *= nums[i];
        }
        
        if (zeros > 1) {
            return answer;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (zeros == 1 && nums[i] == 0) {
                answer[i] = product;
            } else if (zeros == 1 && nums[i] != 0) {
                answer[i] = 0;
            } else {
                answer[i] = product / nums[i];
            }
        }
        return answer;
    }
}