[LeetCode] 238. Product of Array Except Self (자신을 제외한 배열의 곱)

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

현재 인덱스의 값을 제외한 모든 요소의 곱셈 결과가 결과 인덱스 값에 들어갈 때 결과를 출력하라.

• 제한사항 : 시간복잡도 O(n)내에 풀되 나눗셈을 사용하지마라.

✍️ 풀이

---

• 이중 포문은 시간초과가 발생한다.

• 마치 투포인터 비슷한 느낌으로 왼쪽 곱셈 리스트와 오른쪽 곱셈 리스트를 따로 계산해둔다. 이 계산 리스트는 해당 인덱스 값을 제외하고 이전 인덱스까지 곱셈을 나타낸다.
  따라서, 이 두 리스트의 인덱스 값을 곱하면 해당 인덱스를 뺀 전체 요소의 곱셈 결과가 나오게 된다.

🛠 코드

• 리스트를 원소를 앞-뒤로 검사하는 가장 기본적인 풀이방법이다.

---

• 투 포인터 풀이

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        p = 1
        out = []
        # 왼쪽 곱셈 결과
        for i in range(len(nums)):
            out.append(p)
            p *= nums[i]
        
        # 오른쪽 곱셈 결과를 구하는 동시에 out을 재활용해서 결과리스트도 구한다.
        p = 1
        for i in range(len(nums) - 1, -1, -1):
            out[i] *= p
            p *= nums[i]
            
        return out

---

📝 정리

---

🎈 참고

---

Book 링크