[파이썬] 리트코드 238. Product of Array Except Self 풀이

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

Product of Array Except Self - LeetCode

자신을 제외한 모든 수의 곱을 구해야 하는 문제다.

모든 수를 곱한 뒤 자기자신을 나누면 되는 간단한 문제지만, '나누기를 사용해서는 안 된다'고 되어있다. 따라서 다른 방법을 이용해야 한다. 그리고 복잡도를 O(n)으로 제한하고 있기 때문에, 이중 반복문을 이용해서 풀어서도 안 된다. 

정말 어려운 문제고, 나도 풀이를 봐도 잘 이해가 되지 않아서 공부를 위해 글로 정리해보았다 

 

특정 인덱스 기준으로 왼쪽 요소들의 곱과 오른쪽의 요소의 곱을 구하는 것이 핵심이다 

1. 이때 왼쪽 요소들의 곱을 구한 뒤, 거기에 오른쪽 요소를 곱하는 방법은 복잡도 때문에 효율적이지 못하다  

2. 따라서 왼쪽 요소들의 곱을 구한 것에 다시 오른쪽 요소들의 곱을 곱해줘야 한다 

3. 곱을 나타내기 위해 answer리스트를 이용한다. 곱하기 위해서는 answer[0] = 1이어야 한다 

4. 반복문을 이용해서 곱해준다. 오른쪽에서부터 곱할 때는 인덱스를 거꾸로 해 준다 

5. 변수(product)에 이전까지 곱한 값을 저장해두고 이용한다 

 

<왼쪽 요소들의 곱>

index (i)	0	1	2	3
answer	1	1,1	1,1,2	1,1,2,6
nums[i]	1	2	3	4
product	1	2	6	24

왼쪽 요소들의 곱은

- 곱, product는 1에서부터 시작한다 

- 인덱스가 0일 때 

    - 곱 = 1을 answer에 넣어준다 

    - 새 곱은 기존의 곱에 nums[0]을 곱한 값이 된다 

- 인덱스가 1일 때

    - 저장된 곱의 값은 인덱스 1 기준 왼쪽 값들의 곱을 나타낸다. 따라서 answer[1]로 넣어준다 

    - 새 곱은 기존의 곱에 nums[1]을 곱한, nums[0]*nums[1]이 된다

    - 이렇게 곱, product에 왼쪽 수들의 곱이 누적되고, 인덱스가 증가할 때마다 왼쪽 수들의 곱을 answer로 넣어준다 

와 같은 순서로 구해진다 

 

<오른쪽 요소들의 곱>

index (i)	3	2	1	0
answer	1,1,2,6	1,1,8,6	1,12,8,6	24,12,8,6
nums[i]	4	3	2	1
product	4	12	24	24

위와 동일하다. 인덱스가 오른쪽에서부터 거꾸로 가는 것을 나타내기 위해 range(len(nums)-1,-1,-1)로 표현해주었다 

 

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer = []
        product =  1 
        for i in range(0,len(nums)):
            answer.append(product)
            product = product * nums[i]
        product = 1 
        for i in range(len(nums)-1,-1,-1):
            answer[i] = answer[i]*product
            product = product * nums[i]
        return answer
        
 #or 
 '''
 class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        answer = [0]*length
        answer[0] = 1 
        for i in range(1,length):
            answer[i] = nums[i-1]*answer[i-1]
        R = 1
        for i in range(length-1,-1,-1):
            answer[i] = answer[i] * R
            R *= nums[i]
        return answer
 '''