[LeetCode] - 자신을 제외한 배열의 곱

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

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

Product of Array Except Self - LeetCode

 

▶ 입력 

[1,2,3,4]

▶ 출력

[24,12,8, 6]

 

주의 : without using the division operation. (나눗셈을 하지 마라) 

---

풀이) 

 

원래 생각했던 방식은 리스트의 전체 수를 곱한뒤에 자기자신을 나누어주면 되겠구나! 했지만 나눗셈을 하지 말라고 한다..

 

이외의 다른 방법은 한가지 뿐이다. 자기자신을 제외하고 왼쪽의 곱셈결과와 오른쪽의 곱셈결과를 곱하면 구할 수 있다. 

아래 그림과 같이 예를 들면 쉽게 이해할 수 있다. 

이해했으면 코드로 구현해보자 

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

        p = 1 
        result = []

        for i in range(len(nums)) :
            result.append(p)
            p = p * nums[i] 

        p = 1 

        for i in range(len(nums)-1, 0-1 , -1) :
            result[i] = result[i] * p 
            p =  p * nums[i]
        
        return result