[LeetCode] 238. 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.)

---

첫 번째 풀이

문제를 처음 읽자마자 모든 배열의 값을 다 곱해서 해당 index의 값으로 나눠준 다음에 출력하면 되지 않을까? 라며 짧은 생각을 갖고 코드를 짰다.

int[] productExceptSelf1(int[] nums) {
        int numsLength = nums.length;
        int[] result = new int [numsLength];

        int ArrayMultiValue = 1;
        for(int idx = 0; idx < numsLength; idx++){
            ArrayMultiValue *= nums[idx];
        }

        for(int idx = 0; idx < numsLength; idx++){
            result[idx] = ArrayMultiValue / nums[idx];
        }

        return result;
    }

첫 번째 샘플 데이터를 넣어봤을 때 성공!

제출하려던 찰나에 다른 샘플 데이터에 데이터 값이 0이 있는 걸 발견했습니다. 바로 제출 중단 ㅋㅋㅋㅋ

역시 이렇게 쉬울 리가 없지.. 라며 저 0들을 어떻게 하면 좋을까 라고 생각을 해봤다.

그러던 중 2가지를 깨달았다

1. 한 번이라도 0이 곱해지면 값은 0이 되는구나!

2. InputArr에서 0의 개수가 중요하겠구나

    a. 0의 개수를 카운팅 2개 이상이면 모든 배열이 0이 된다.

    b. 0이 1개라면 해당 배열 빼고 모두 0

    c. 0이 한 개도 없다면 첫 번째 풀이로 하면 되겠다

 

두 번째 풀이

public int[] productExceptSelf(int[] nums) {
        int numsLength = nums.length;
        int[] result = new int[numsLength];
        ArrayList<Integer> zeroIdxArr = new ArrayList<Integer>();
        int multiVal = 1;

        for(int idx = 0; idx < numsLength; idx++){
            result[idx] = 0;
            if(nums[idx] == 0){
                zeroIdxArr.add(idx);
            }else{
                multiVal *= nums[idx];
            }
        }
        int zeroIdxArrSize = zeroIdxArr.size();

        if(zeroIdxArrSize > 1) {
            return result;
        } else if(zeroIdxArrSize == 1){
            int idx = zeroIdxArr.get(0);
            result[idx] = multiVal;
        } else{
            for(int idx =0; idx < numsLength; idx++){
                result[idx] = multiVal / nums[idx];
            }
        }
        return result;
    }

시간 복잡도를 최대한 줄이기 위해서 첫 번째 반복문에서 배열을 초기화해주고 배열 전체의 값을 뽑아봤다.

결과는!

성공!!

풀 리퀘 날리러 가야지~!