[파이썬 알고리즘 인터뷰] 11. 자신을 제외한 배열의 곱

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브

 

---

11. 자신을 제외한 배열의 곱

리트코드 238. Product of Array Except Self 문제입니다.

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

 

 

풀이

 모든 nums 값을 곱한 다음에 nums[i]로 나눠주는 풀이를 떠올렸지만, 나눗셈을 하지 않는 제약조건이 있어서 다른 방법을 생각해야 했습니다. 도저히 생각이 안나서 책에 있는 풀이를 참고했습니다.

 

 책에는 왼쪽 곱셈 결과에 오른쪽 곱셈 결과를 곱하는 풀이방법이 나와있었습니다.

 

def productExceptSelf(self, nums):
    p = 1
    out = []
    for i in range(len(nums)):
        out.append(p)
        p *= nums[i]

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

    return out