[알고리즘][배열] - 6. 자신을 제외한 배열의 곱

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님'을 보고 작성되었습니다.

---

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

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

---

 

[왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈]

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

        #왼쪽 곱셈 [1,1,2,6]
        for i in range(len(nums)):
            answer.append(p)
            p = nums[i] * p
        p = 1 #재사용을 위함

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

• 이 문제의 주요 제약사항은 나눗셈을 하지 않고 O(n)에 풀이하라는 것이다.
• 이 말은 미리 전체 곱셈 값을 구해놓은 뒤 각 항목별로 자기 자신을 나눠서 풀이하는 방법은 안 된다는 뜻이기도 하다.
• 그렇다면 풀이 방법은 한 가지 뿐이다.
  • 자기 자신을 제외하고 왼쪽의 곱셈 결과와 오른쪽의 곱셈 결과를 곱해야 한다.
• 위의 설명대로 왼쪽에 둔 값들을 모두 곱해놨던 리스트를 만들어 그 리스트를 맨 오른쪽부터 돌면서 곱해주는 걸로 한다 이때 P라는 변수를 이용해 왼쪽 오른쪽 값을 구해준다.