Products of Array Except Self

Products of Array Except Self:
https://neetcode.io/problems/products-of-array-discluding-self/question

문제이해

• 각 위치 i에 대해, 자기 자신을 제외한 나머지 모든 숫자의 곱을 구함.
  입력은 정수 배열 nums, 출력은 같은 길이의 배열 output
• output[i] = nums[i]를 뺀 나머지 모든 원소의 곱

문제 핵심

• 배열을 한 번 이상 순차적으로 처리할 수 있는지.
  나눗셈 없이 문제를 논리적으로 분해할 수 있는지.
  0처리와 같은 엣지 케이스들을 고려하는지.

문제 풀이 - 노답 풀이

처음에 Brute Force로 O(n^2) 으로 풀기
math 내장함수의 prod() 사용

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        import math
        ans = []
        for i in range(len(nums)):
            left = math.prod(nums[:i])
            right = math.prod(nums[i+1:])
            ans.append(left*right)
        return ans

-> math.prod(nums[:i]) -> O(n)
math.prod(nums[i+1:]) -> O(n)
이걸 n 번 반복하기 때문에 O(n^2)가 됨.
위와 같은 로직은 매 반복마다 새로운 리스트를 생성해서 메모리 낭비와 성능 저하를 일으킬 수 있음.
같은 곱을 계속 다시 계산하고 있는데, 이전 계산 결과를 재사용하는 방안으로 가야함

사고 흐름

• 가장 처음에 생각한건 모든 수를 곱한 뒤에 output[i] = 전체 곱 / nums[i] -> 문제에서 without using the division operation
  나눗셈 사용을 금지했으며, 특히 원소 안에 0이 나오면 해당 방법은 불가능
• 관점을 전환해서 nums[i]를 제외한 모든 곱은 (i 왼쪽에 있는 숫자들의 곱) x (i 오른쪽에 있는 숫자들의 곱) 으로 생각하면 됨
• 그래서 왼쪽에서부터 누적 곱 배열을 만들고 left[i] = i 왼쪽에 있는 값들의 곱), 오른쪽에서부터 누적 곱 배열을 만들어서 (right[i] = i 오른쪽에 있는 값들의 곱) 으로 output[i] = left[i] x right[i] 으로 하면 시간복잡도 O(n)

이 문제의 핵심 ADT

• Array(순차 자료 구조)
  -> 배열을 한 방향으로 누적 처리할 수 있는지?
  이전 계산 결과를 저장해서 재사용할 수 있는지?
  : 이 문제는 Prefix / Suffix 누적 연산 문제임.

개선

left, right 두 개의 보조 배열을 만들어서, 누적 곱을 사용함

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)

        left = [1] * n
        right = [1] * n
        ans = [1] * n

        for i in range(1, n):
            left[i] = left[i-1] * nums[i-1]
        
        for i in range(n-2, -1, -1):
            right[i] = right[i+1] * nums[i+1]
        
        for i in range(n):
            ans[i] = left[i] * right[i]

        return ans

-> 시간복잡도 O(n), 공간복잡도 O(n )

여기서 공간복잡도를 좀 더 줄이고 싶다면?
left 배열을 반환할 결과 배열에 바로 저장하고
right 배열을 변수 하나 postfix로 대체함

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [1] * n

        prefix = 1
        for i in range(n):
            ans[i] = prefix
            prefix *= nums[i]

        postfix = 1
        for i in range(n-1, -1, -1):
            ans[i] *= postfix
            postfix *= nums[i]


        return ans
        

left[i]는 ans[i]에 미리 있고, right[i]만 뒤에서 오면서 곱해주면 됨

처음엔 left/right 배열로 풀고, left는 output에 저장하고 right는 postfix 변수로 처리해서 공간을 O(1)로 줄일 수 있다.

이렇게 되면 시간복잡도 O(n), 공간복잡도 O(1)로 풀어나갈 수 있음.