[LeetCode] 238. Product of Array Except Self (파이썬)

238. Product of Array Except Self - 파이썬 풀이

• 해당문제 링크

  목차

1. 문제풀이 아이디어
2. 구현코드

문제풀이 아이디어

• 일단 해당 문제는 O(n) 시간 복잡도로 풀어야한다는 조건이 있고 나눗셈을 쓸 수 없다.
• 그렇다면 시간 초과가 나지 않기 위해서는 3N 이런식은 상관없는데 N^2가 되면 안된다. 그럼 각 인덱스에서 곱하기를 계산하고 있으면 안된다는 의미이다.
• 그래서 여기서 구간 합을 이용할 것이다.
  • 구간합이란 a라는 인덱스에서 b란 인덱스 까지의 합을 의미한다.
  • 부분합은 0에서 b란 인덱스까지의 합을 의미하는 것이다.
• 만약 내가 어떤 구간 합을 구하고 싶으면 보통 해당 인덱스부터 반복을 통해서 마지막 인덱스까지의 합을 구하는 것을 생각할 것이다.
• 하지만 이 방법은 모든 인덱스마다의 구간합이나 부분합을 구하고 싶을 땐 굉장히 효율적이지 못하다.
• 그래서 만약 사전에 각 인덱스까지의 부분합을 구해놓고 배열에 저장해놨다면 a ~ b 구간 합은 arr[b] - arr[a-1]로 구할 수 있을 것이다. 이 문제도 이런 개념을 이용할 것이다.
• 사전에 각 인덱스의 부분곱 0-k까지를 저장해놓고 reverse 부분곱도 구해놓는다. 마지막 인덱스부터 현 인덱스까지의 곱이다.
• 그랬을때 구간 곱은 현재 인덱스 전까지의 부분곱과 다음 인덱스의 reverse 부분곱을 곱하면 내가 원하는 현재 인덱스를 제외한 구간 곱이 나올 것이다.

구현코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        product = [0]*len(nums)
        r_product = [0]*len(nums)
        for i,n in enumerate(nums):
            if i == 0:
                product[i] = n # 부분 곱
                r_product[len(nums)-1-i] = nums[len(nums)-1-i] # reverse 부분 곱
            else:
                product[i] = product[i-1] * n
                r_product[len(nums)-1-i] = r_product[len(nums)-i] * nums[len(nums)-1-i]
        result = []
        for i in range(len(nums)):
            left = product[i-1] if i-1 >= 0 else 1
            right = r_product[i+1] if i+1 < len(nums) else 1
            result.append(left*right)
        return result