배열의 곱셈 제외하기 - 238. Product of Array Except Self

238. 배열의 곱셈 제외하기

정수 배열 nums가 주어졌을 때, answer[i]가 nums[i]를 제외한 모든 요소들의 곱과 같도록 하는 배열 answer를 반환하세요.

nums의 어느 접두사나 접미사의 곱셈 결과도 32비트 정수에 들어갈 수 있다고 보장됩니다.

O(n) 시간 복잡도로 동작하는 알고리즘을 작성해야 하며, 나눗셈 연산을 사용하지 않아야 합니다.

예제 1:

• 입력: nums = [1,2,3,4]
• 출력: [24,12,8,6]

예제 2:

• 입력: nums = [-1,1,0,-3,3]
• 출력: [0,0,9,0,0]

제약 조건:

• nums.length는 2 이상 105 이하입니다.
• nums[i]는 -30 이상 30 이하입니다.
• nums의 어느 접두사나 접미사의 곱셈 결과도 32비트 정수에 들어갈 수 있다고 보장됩니다.

추가 과제:

O(1) 추가 공간 복잡도로 문제를 해결할 수 있습니까? (출력 배열은 공간 복잡도 분석에서 추가 공간으로 계산하지 않습니다.)

 

 

풀이

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
    
        # 정답 배열을 초기화합니다.
        answer = [1] * n
        
        # 왼쪽 곱을 계산합니다.
        left_product = 1
        for i in range(n):
            answer[i] = left_product
            left_product *= nums[i]
        
        # 오른쪽 곱을 계산하면서 정답 배열을 업데이트합니다.
        right_product = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= right_product
            right_product *= nums[i]
        
        return answer