문제이동
난이도 : ⭐️⭐️

첫 번째 제출
리스트 남발하기 - 공간복잡도 O(n)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # 아니 이걸 어케 생각하지 천재인가
        # i의 이전 값까지의 곱으로 구성된 리스트 x 이후 값의 곱으로 구성된 리스트
        # 1. ->
        pre_mul, post_mul = list(), list()
        cur = 1  
        for i in range(len(nums)):
            pre_mul.append(cur)
            cur *= nums[i]
        # 2. <-
        cur = 1
        for i in range(len(nums)-1, -1, -1):
            post_mul.append(cur)
            cur *= nums[i]
        # 3. 1 x 2 
        result = list()
        for i in range(len(nums)):
            result.append(pre_mul[i] * post_mul[len(nums)-1-i])
        
        return result

Runtime : 268 ms
Memory : 22.4 MB

힌트를 보고 곰곰히 생각하다가 풀었다.
(필기한 건 스캔해놨지만 올리진 않겠다)
하지만 정답을 보고 공간복잡도가 별루였다.

두 번째 제출

리스트 하나만 쓰기 - 공간복잡도 O(1)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # i의 이전 값까지의 곱으로 구성된 리스트 x 이후 값의 곱으로 구성된 리스트
        result = list()
        # 1. ->
        p = 1
        for i in range(len(nums)):
            result.append(p)
            p *= nums[i]
        
        # 2. <-
        p = 1
        for i in range(len(nums)-1, -1, -1):
            result[i] *= p
            p *= nums[i]

        return result

Runtime : 230 ms
Memory : 21.1 MB

+)

• i 이전 값들의 곱이 원소인 리스트 하나 (nums[:i]의 곱이 한 원소)
• i 이후 값들의 곱이 원소인 리스트 하나 (nums[i+1:])
• 위에 두 리스트의 곱이 정답 (i를 제외한 값들의 곱이 하나의 원소가 됨)

하지만 3가지의 list를 만드는 건 공간복잡도만 높아진다.

=> 1,2 번 할 때마다 output 리스트에 곱해주는 식으로 하면 하나의 list로도 가능하다!!