[python] 238. Product of Array Except Self

Product of Array Except Self - LeetCode

Product of Array Except Self - LeetCode

 

자신을 제외한 배열의 곱 

 

제시된 배열에서 자신을 제외한 값들을 곱한 값들을 리턴하는 문제 

 

주의!! 나눗셈 금지 조건 존재 

배열의 모든 값들의 곱을 구하고 자기 자신으로 나누는 풀이는 불가! 

 

풀이

 

옳은 풀이 

 

자기 자신을 제외한

왼쪽 값들의 곱셈 결과와 

오른쪽 값들의 곱을 곱하면 올바른 풀이를 할 수 있다. 

 

1. 자기 자신을 제외한 왼쪽 값들의 곱 

 

mul = 1 # 곱셈이기에 초깃값이 1이 되어야 한다 
for i in range(len(nums)):
	result.appand(mul) # 자신을 제외한 왼쪽 값들의 곱들이 들어간다 
    mul *= nums[i] # 여기서 이전 값들의 곱이 쌓인다

 

2. 자기 자신을 제외한 오른쪽 값들의 곱 

 

mul = 1
for i in range(len(nums)-1, 0 -1, -1):
	# (start, stop, step) stop은 범위 미포함이라 -1 해줘야 한다 
    result[i] *= mul # 왼쪽에서 곱해져온 값에 또 곱해야 한다 
    mul *= nums[i]

 

3. 완성된 코드 

 

from typing import List
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = []
        mul = 1
        for i in range(len(nums)):
            result.append(mul)
            mul *= nums[i]
        mul = 1

        for i in range(len(nums)-1, 0 -1, -1):
            result[i] *= mul
            mul *= nums[i]
                    return result

s = Solution()
print(s.productExceptSelf([1,2,3,4]))
print(s.productExceptSelf([-1,1,0,-3,3]))
print(s.productExceptSelf([0, 0]))
print(s.productExceptSelf([0, 4, 0]))

 

옳지 않은 풀이

 

모든 값들을 곱하여 자기 자신으로 나누려고 시도 (조건에 맞지 않음)

 

from typing import List
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        mul = 1
        for num in nums:
            if nums.count(0) > 1:
                mul = 0
            if num != 0:
                mul *= num
            # 전부 0만 들어있는 배열이 들어왔을 때 오류 
            # -> set 으로 처리
            # set(nums) == {0}

            # 0이 2개 이상 들어있는 배열은 ?
            # 항상 값이 0이 된다 
            # if nums.count(0) > 1: 로 위의 질문과 한번에 처리
        for num in nums:
            if 0 in nums:
                if num != 0:
                    result.append(0)
                else:
                    result.append(mul)
            else:
                result.append(mul//num)
        return result

 

위 코드가 타임 아웃이 되었다 

(타임 아웃도 문제인데 조건이 아예 맞지 않은 풀이)

 

타임 아웃이 되어 자기 자신을 제외한 배열을 인덱싱을 사용하여 만들었다 

from typing import List
class Solution:
	def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = []
        for i in range(len(nums)):
            new_nums = nums[:i] + nums[i+1:]
            mul = 1
            for num in new_nums:
                mul *= num
            result.append(mul)
        return result