[LeetCode/릿코드] - 238. Product of Array Except Self (Medium/미디엄)

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.

문제 해설:

1. 정수 숫자 배열이 주어진다.
2. 자기 자신을 제외한 모든 배열 값의 곱을 배열의 각 자리에 넣어서 반환한다.

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.)

* 공간을 사용하지 않고 바로 반환하는 방법을 생각해봐야 하는데, 내가 짠 코드에서 그냥 nums에 넣고 리턴하면 될 것 같다.

<풀이 아이디어>
1. O(n) 이기 때문에 반복문을 이중으로 쓰면 안됨 만 x 만은 1억이기 때문에 시간제한 초과.
2. 맨 처음 모든 값을 곱하고 자기 자신(숫자)을 나눠 주는 것을 생각.
3. 예외는 마이너스와 0이 있을 거라고 추측.
4. 전체 배열의 값을 모두 곱해서, 해당 자리 값을 나누는 방법을 고안.
5. 4번 방식이면 마이너스는 스스로 해결.
6. 0을 생각해봤을때, 0이 1개일때는 총 곱 값에 0을 제외하고 곱한 다음에 0이 아닌 자리에 0을 넣으면 됨.
7. 0이 2개 이상일때는 모두 0이 됨.

* 전체 곱을 구해서 해당 자리의 값을 나눠 나가면서 답배열에 넣으면 해결 가능.

 

<정답 코드>

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        nLen = len(nums)
        ans = [1] * nLen
        pro = nums[0]
        zCnt = 0
        
        for i in range(1,nLen):
            if nums[i] != 0:
                pro *= nums[i]
                #print(i,": pro =", pro)
            else:
                zCnt += 1
        #print("p:", pro, "z:", zCnt)
        
        for i in range(nLen):
            if zCnt > 1:
                ans[i] = 0
            elif zCnt > 0 and nums[i] != 0:
                ans[i] = 0
            elif nums[i] == 0:
                ans[i] = pro
            else:
                ans[i] = pro // nums[i]
            
        #print(ans)
        return ans