[LeetCode] 238. Product of Array Except Sell

1. 문제

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

Product of Array Except Self - LeetCode

2. 접근 방법

 ㄷㄷㅣ용

O(n)으로 하려면 그냥 다 곱해놓고 하나씩 나누면 되게따 했는데, 뒤에 나누기를 사용하지 말라구 되어있다 ^-^

 

음 ~!

 

그래서 또 투포인터같이 ?

왼쪽에서부터 하나씩 다 곱하고, 

오른쪽에서부터 하나씩 다 곱하고, 해당 idx까지 곱한 값에 왼쪽에서부터 곱한 값을 곱해준다.

 

이렇게 되면 O(2n) 이니까 시간복잡도는 O(n)이고,

공간 복잡도도 O(1)로 만들 수 있다.

 

처음에 이게 왜 공간 복잡도가 O(1)이지 ?!!??!?! O(n)아닌가 했는데

출력에 필요한 공간은 공간 복잡도에 포함하지 않는다구 한다.

 

어차피 지금 왼쪽에서부터 곱한 값을 넣어놓는 공간인 answer는 결국 출력에 사용하는 공간이기 때문에

 

공간 복잡도는 O(1)이 됩니다.

 

3. 코드

python

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer = []
        temp = 1

        for i in range(len(nums)):
            answer.append(temp)
            temp *= nums[i]
        temp = 1

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

4. 마치며

재밌는 알고리즘 ^_^