릿코드 238. Product of Array Except Self

이 글은 Tistory에서 이전된 포스팅입니다. 원본은 여기에서 확인할 수 있습니다.

문제

https://leetcode.com/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-interview-150

접근

나누기를 하지 않고 O(n) 연산을 하라는 것에 아이디어가 안떠올랐다. Discussion 슬쩍 열어보고 left, right 단어보고 떠올랐다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left_dp, right_dp = [0], [0]
        left_product, right_product = 1, 1
        for i in nums:
            left_product *= i
            left_dp.append(left_product)

        for i in range(len(nums)-1, -1, -1):
            right_product *= nums[i]
            right_dp.append(right_product)
        
        result = []
        leng = len(nums)
        for i in range(leng):
            if i-1 < 0:
                left = 1
            else:
                left = left_dp[i]
            
            if i+1 >= leng:
                right = 1
            else:
                right = right_dp[leng-i-1]
            result.append(left * right)
        return result

left_dp와 right_dp를 먼저 만들고 idx를 기점으로 좌우 dp를 곱했다.

이렇게 풀었을 때, 백분율 시간이 조금 아쉬웠다.

다른 코드를 한 번 열어보니 위에 풀이에서 마지막 for없이 result를 만들었다. 생각해보니, length가 4인 nums에서

left가 1칸이면 right는 2칸이고

left가 2칸이면 right는 1칸이고

…

정해져 있기 때문에 마지막에 굳이 for문이 없어도 result를 만들 수 있다.

수정 코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        dp = [1]
        left_product, right_product = 1, 1
        leng = len(nums)
        for i in range(leng-1):
            left_product *= nums[i]
            dp.append(left_product)

        # print(dp)
        for i in range(len(nums)-1, 0, -1):
            right_product *= nums[i]
            dp[i-1] *= right_product
        
        return dp