[LeetCode 75] Medium - 238. Product of Array Except Self ☆

238. Product of Array Except Self

 

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

 

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

 

Constraints:

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

 

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

 

문제 풀이

이 문제는 주어진 배열 nums에서, 각 요소를 제외한 나머지 요소들의 곱을 계산하여 결과 배열을 반환하는 문제입니다. 나눗셈 없이, 시간 복잡도 O(n) 로 해결해야 합니다.

---

문제 조건

1. 각 answer[i] 는 배열 nums의 i 번째 요소를 제외한 나머지 요소들의 곱입니다.
2. 나눗셈 사용 금지: 단순히 배열 전체 곱을 구한 뒤 각 요소로 나누는 방식은 사용할 수 없습니다.
3. 시간 복잡도는 O(n), 공간 복잡도는 O(1) 추가 공간(결과 배열은 제외).

풀이 방법

1. 아이디어

배열의 곱을 효율적으로 계산하려면 다음과 같은 접근법을 사용할 수 있습니다:

• 왼쪽 누적 곱 (prefix product): 각 요소 iii에서, 왼쪽에 있는 모든 요소들의 곱.
• 오른쪽 누적 곱 (suffix product): 각 요소 iii에서, 오른쪽에 있는 모든 요소들의 곱.
• 결과는 왼쪽 곱 × 오른쪽 곱으로 계산할 수 있습니다.

2. 구현 과정

1. 배열의 크기를 nnn이라고 할 때:
   • 왼쪽 곱 배열 left : left[i] 는 nums[i] 왼쪽의 곱.
   • 오른쪽 곱 배열 right : right[i] 는 nums[i] 오른쪽의 곱.
2. 최종 결과 answer[i] = left[i] × right[i] .
3. 공간 최적화: left 와 right 배열 대신 하나의 배열 answer와 추가 변수 두 개로 처리.

 

내가 다시 푼 코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        leftM = [1] * len(nums)
        
        rightM = [1] * len(nums)
        ans = [1] * len(nums)

        for i in range(len(nums)-1):
            leftM[i+1] *= leftM[i] * nums[i]

        for i in range(len(nums)-1, 0, -1):
            rightM[i-1] *= nums[i] * rightM[i]
        
        for i in range(len(nums)):
            ans[i] = leftM[i] * rightM[i]
        return ans

 

1. 나눗셈 사용 금지: 만족
2. 시간 복잡도: for 문 3개로 3 × O(n) 으로 즉, O(n) 만족
3. 공간 복잡도: 그러나, 결과 공간 제외하고, n 크기의 leftM, rightM 배열 생성하여 2 × O(n), 즉, O(n) 임
   1. O(1) 추가 공간(결과 배열은 제외) : 불만족

 

https://youtu.be/V_De_bhXKzc?si=llCLzgmLGkh_ZsgF

 

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        answer = [1] * n  # 결과 배열 초기화 (1로 채움)
        
        # 왼쪽 곱 계산
        left_product = 1
        for i in range(n):
            answer[i] = left_product  # 현재 위치에 왼쪽 곱 저장
            left_product *= nums[i]  # 왼쪽 곱 업데이트
        
        # 오른쪽 곱 계산
        right_product = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= right_product  # 왼쪽 곱에 오른쪽 곱 곱하기
            right_product *= nums[i]  # 오른쪽 곱 업데이트
        
        return answer