리트코드 - 238. Product of Array Except Self

정수 배열 nums가 주어졌을 때, answer[i]가 nums[i]를 제외한 nums의 모든 요소의 곱과 같도록 배열의 답을 반환한다.
nums의 접두사 또는 접미사의 곱은 32비트 정수에 맞도록 보장된다.
나누기 연산을 사용하지 않고 O(n) 시간 내에 실행되는 알고리즘을 작성해야 한다.

 

풀이 1.

이 문제를 해결하기 위한 접근법은 두 개의 패스를 사용하는 것이다.

첫 번째 패스에서는 각 인덱스의 왼쪽에 있는 모든 숫자들의 곱을 계산하고, 두 번째 패스에서는 각 인덱스의 오른쪽에 있는 모든 숫자들의 곱을 계산한다.

마지막으로, 각 인덱스에 대해 이 두 개의 값(왼쪽 곱과 오른쪽 곱)을 곱한다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums) # O(1)
    
        L = [0]*length # O(1)
        L[0] = 1 # O(1)
        for i in range(1, length): # O(n)
            L[i] = nums[i - 1] * L[i - 1]
        
        # 오른쪽 곱셈 결과를 저장할 배열
        R = [0]*length # O(1)
        R[length - 1] = 1 # O(1)
        for i in reversed(range(length - 1)): # O(n)
            R[i] = nums[i + 1] * R[i + 1] # O(1)
        
        # 결과 배열
        answer = [0]*length # O(1)
        for i in range(length): # O(n)
            answer[i] = L[i] * R[i] # O(1)
            
        return answer

 

 

각 루프는 n번 순회합니다 (n은 nums의 길이). 따라서 전체 시간 복잡도는 O(n)이다.

두 개의 추가 배열(L과 R)을 사용하므로 공간 복잡도는 O(n)이다.

풀이 2.

O(1) 추가 공간 복잡도로 이 문제를 해결하기 위해서는 출력 배열을 제외하고 추가적인 공간을 사용하지 않는 방식으로 접근해야 한다.

이를 위해, 출력 배열 answer를 사용하여 먼저 왼쪽 요소들의 곱을 계산한 후, 오른쪽 요소들의 곱을 계산하면서 바로 결과를 업데이트한다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums) # O(1)
        answer = [0]*length # O(n)
        answer[0] = 1

        for i in range(1, length): # O(n)
            answer[i] = nums[i - 1] * answer[i - 1] # O(1)

        R = 1

        for i in reversed(range(length)): # O(n)
            answer[i] = answer[i] * R # O(1)
            R *= nums[i] # O(1)

        return answer

 

이 코드는 추가 배열 없이 오직 answer 배열과 변수 R을 사용하여 각 요소의 왼쪽과 오른쪽 요소들의 곱을 계산한다.

이 방법은 출력 배열을 제외하고 O(1)의 추가 공간 복잡도를 가진다.