11. Product of Array Except Self

리트코드

• 배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라

• 제약사항: 나눗셈을 하지 않고 O(n)에 풀이하라
  (미리 전체 곱셈 값을 구해놓고 각 항목별로 자기 자신을 나눠서 풀이하는 방법은 안된다는 뜻이기도 하다.)

1. 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈

• 자기 자신을 제외하고 왼쪽의 곱셈 결과와 오른쪽의 곱셈 결과를 곱해야한다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        out = []
        p = 1
        
        #왼쪽 곱셈
        
        for i in range(0, len(nums)):
            out.append(p)
            p = p * nums[i]
        
        p = 1
        
        #왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
        
        for i in range(len(nums) -1, 0 - 1, -1):
            out[i] = out[i] * p
            p = p * nums[i]
        
        return out
        

• 먼저 왼쪽부터 곱해서 result에 추가한다.

• 곱셈 결과는 그대로 out 리스트 변수에 담기게 되며, 마지막 값 곱셈을 제외하여 결과는 [1,1,2,6]이 된다.

• 이 처럼 변수가 오른쪽으로 이동하면서 해당 인덱스의 값을 곱해 나간 다음, 오른쪽에서 곱해서 넣는다.

  • 만약 별도의 리스트 변수를 만들고 그 변수에 우측 곱셈 결과를 넣으면, 공간 복잡도는 O(n)이 된다.
  • 그러나, 기존 out 변수를 재활용한다면 공간 복잡도는 O(1)에 풀이가 가능하다.
    (참고로 출력에 필요한 공간은 공간 복잡도에 포함하지 않는다)

• 다음으로 왼쪽의 곱셈 결과에 오른쪽 마지막 값부터 차례대로 곱해 나간다.

• range (x, y, z)에서 세번째 파라미터 z는 증분을 지정하는 파라미터이며, 여기서는 -1이므로, 1씩 줄어드는 형태가 된다.

• 여기서 p는 1부터 차례대로 점점 커지면서 4, 12, 24가 되고, 최종적으로 이 값이 왼쪽 곱셈 결과에 곱해져 out 변수에는 정답인 [24, 12, 8, 6]을 담게 된다.