배열 [리트코드] 238. Product of Array Except Self

Division 사용한 풀이

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        all_product = 1
        num_of_zero = nums.count(0)
        ans = [0 for i in range(len(nums))]


        for i in range(len(nums)):
            if nums[i]!=0:
                all_product*=nums[i]

        if num_of_zero==1:
            for i in range(len(nums)):
                if nums[i]==0:
                    ans[i]=all_product
        elif num_of_zero>1:
            pass
        else:
            ans = [all_product//nums[i] for i in range(len(nums))]

        return ans



solution = Solution()
print(Solution.productExceptSelf(solution,
[0,1]))

전체를 다 곱하고 0 이 아닌 경우에 값을 나눠주도록 하면 시간복잡도 0n으로 가능.
나눗셈을 안 사용하고 어떻게 풀 수 있을까?

바로 각각 요소의 자신을 제외한 왼쪽 부분곱, 오른쪽 부분곱을 곱하는 것이다.

Division 미사용, 오른쪽 왼쪽의 부분곱을 이용하여 풀이

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        prod_left, prod_right = 1,1
        ans = [1]

        for i in range(1,len(nums)):
            prod_left*=nums[i-1]
            ans.append(prod_left)
        for i in range(len(nums)-2,-1,-1):
            prod_right*=nums[i+1]
            ans[i]*=prod_right
        # print("right list is", prod_right_list)

        return ans


solution = Solution()
print(Solution.productExceptSelf(solution,
[1,2,3,4]))