리트코드] 238. Product of Array Except Self

[문제]

https://leetcode.com/problems/product-of-array-except-self/

Product of Array Except Self - LeetCode

[코드]

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        sol = []
        product =  1
        for i in range(len(nums)):
            sol.append(product)
            product = product * nums[i]
            print(str(product) + " " + str(sol))
        product = 1
        for i in range(len(nums)-1,-1,-1):
            sol[i] = sol[i]*product
            product = product * nums[i]
        return sol

[결과]

Success
Details
Runtime: 264 ms, faster than 66.69% of Python3 online submissions for Product of Array Except Self.
Memory Usage: 21.1 MB, less than 56.67% of Python3 online submissions for Product of Array Except Self.
Next challenges:

 

[풀이]

• 화가나는 문제였다. 도저히 풀이를 알 수 없어 답지를 봤다.
• O(n^2) 의 시간복잡도 였으면 금방 풀었을 것 같다.
• O(n)을 만족하기 위해선 loop문을 한번만 실행 해야 했다.
• 정답은 자신의 왼쪽에 있는 모든 수의 곱을 구하고, 오른쪽에 있는 모든 수의 곱을 구해 곱하는 것이었다.
• 아래에서 간단히 설명 해 보겠다.

[  2  1 3 4] 라는 배열이 있다고 가정

[  1  2 2 6] : 각 인덱스의 왼쪽의 모든 수를 곱한 배열

[12 12 4 1] : 각 인덱스의 오른쪽의 모든 수를 곱한 배열

[12 24 8 6] : 정답

 

[교훈]

• 모르면 배우자