문제

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.

구현 전 예상 풀이

• 0 개수가 없을때
  • 전체 곱에서 해당 인덱스의 값을 나눈다.
• 0이 1개 일때
  • 0 인덱스는 나머지 숫자의 곱
  • 0외의 인덱스는 0
• 0이 2개 이상일때
  • 모든 값이 0

구현 코드

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int zeroIdx = -1;
        int total = 1;
        int[] result = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];

            if (num == 0) {
                if (zeroIdx != -1) {
                    return result;
                }

                zeroIdx = i;
                continue;
            }

            total *= num;
        }

        if (zeroIdx != -1) {
            result[zeroIdx] = total;
            return result;
        }

        for (int i = 0; i < nums.length; i++) {
            result[i] = total / nums[i];
        }

        return result;
    }
}

다른 사람 풀이

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int ans[] = new int[n];
        
        for(int i = 0; i < n; i++) {
            int pro = 1;
            for(int j = 0; j < n; j++) {
                if(i == j) continue;
                pro *= nums[j];
            }
            ans[i] = pro;
        }
        
        return ans;
    }
}

브루트포스로도 풀린다

238. Product of Array Except Self
다른 사람 풀이 링크