1주차 - 238. Product of Array Except Self [코딩 인터뷰 공부]

LeetCode 리트코드 문제 공부

 

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

 

정수로 주어진 배열 nums을 이용하여 nums[i] 요소를 제외한 나머지 요소들의 곱인 answer[i] 로 이루어진 새 배열 answer 을 return 하세요.

나누기를 이용하지 않으며 O(n) 시간 복잡도인 알고리즘이어야 합니다.

 

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

.

.

.

.

.

.

겨우 해냈습니다.

tmp = 1 을 놓지 못하여 오랜 시간 고전했습니다.

answer = [1] * len(nums)
        
        for i in range(1,len(nums)):
            answer[i] = answer[i-1] * nums[i-1]
        tmp = 1
        for i in range(len(nums)-2, -1, -1):
            tmp *= nums[i+1]
            answer[i] *= tmp
            
        return answer

런타임: 264ms, 62.30%

메모리 사용: 21MB, 35.67%

.

.

.

ans=[]
product=1
for i in nums:
    ans.append(product)
    product*=i
product=1
for i in range(len(nums)-1,-1,-1):
    ans[i]=ans[i]*product
    product*=nums[i]
return ans

런타임: 176ms, 99.34%

메모리 사용: 21MB, 37.80%