Product of Array

Product of Array Except Self

• Given : 정수 배열 nums[i]
• Return : 정수 배열 answer[i] 는 nums의 nums[i] 를 제외하고 곱한 값
• 나눗셈을 사용할수 없고 O(n) 으로 풀이

Solution

• 수를 왼쪽부터 곱셈한 결과와 오른쪽부터 곱셈한 결과를 기록
• 각 요소에 대해서 기록된 값을 바탕으로 자신을 제외하고 곱한값 계산

Code

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        size = len(nums)
        lefts=[1]*size
        rights=[1]*size

        for i in range(size-1):
            lefts[i+1] = lefts[i] * nums[i]
            rights[i+1] = rights[i] * nums[size-1-i]

        return ( lefts[i]* rights[size-1-i] for i in range(size))

Code2

• 배열 1개만 사용하기

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        size = len(nums)
        result=[1]*size

        for i in range(size-1):
            result[i+1] = result[i] * nums[i]

        tmp = 1
        for i in range(size-1):
            tmp = tmp * nums[size-1-i]
            result[size-2-i] *= tmp

        return result