[LEET CODE] 238. Product of Array Except Self

# Problem

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. * 나눗셈을 하지 않고 O(n)에 풀이하라 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.

 

# My Answer

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer =[]
        pnum = 1 # 값들의 곱
        zero=0 # 배열의 0의 개수
        for num in nums:
            if num!=0: # 0이 1개인 경우 값들의 곱을 계산하기 위해서 0은 제외
                pnum *= num
            else:
                zero+=1 # 배열에 있는 0의 개수 세기
        
        # 문제에서 나눗셈 쓰지 말라고함..
        if zero==0: # 배열에 0이 없다면 전체곱을 각각의 수로 나누면 나머지들의 곱이다.
            for num in nums:
                answer.append(pnum//num)
        elif zero==1: # 배열에 0이 하나라면 0인 인덱스 제외 다른 인덱스들의 값은 모두 0이다
            for num in nums:
                if num==0:
                    answer.append(pnum)
                else:
                    answer.append(0)
        else: # 배열에 0이 1개 이상이라면 자신을 제외한 곱은 항상 0이 된다
            answer = [0]*len(nums)
        return answer

 

# Solution 1 - 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        out = []
        p = 1
        # 왼쪽 곱셈
        for i in range(0, len(nums)):
            out.append(p)
            p = p * nums[i]
        p = 1
        # 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
        for i in range(len(nums) - 1, 0 - 1, -1): # 오른쪽부터 하나씩 줄어서 0까지이므로 0까지 포함하려면 0-1을 해줘야한다.
            out[i] = out[i] * p
            p = p * nums[i]
        return out

자기 자신을 기준으로 왼쪽의 곱셈 결과와 오른쪽의 곱셈결과를 곱한다.

왼쪽 곱셈결과를 구한 후 오른쪽부터 왼쪽의 결과값에 곱해준다.