[2024] day 76. Leetcode 238. Product of Array Except Self

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 15일 (금)
Leetcode daily problem

238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/description/?source=submission-ac

Problem

정수로 구성된 배열이 주어질 때, 해당 배열의 인덱스를 제외한 나머지 원소의 곱으로 구성된 최종 배열을 반환한다.

Solution

array

해당 문제를 효율적으로 풀기 위해서는 배열의 해당 인덱스를 기준으로 왼쪽곱셈합, 오른쪽곱셈합을 계산한 후 이 값들을 이용해서 배열을 업데이트 하는 것이다.

배열을 왼쪽에서 한번 끝까지 순환하고, 오른쪽끝에서 첫 번쨰 인덱스 까지 한번씩 순환하면서 왼쪽 곱셈합과 오른쪽곱셈합을 이용해서, 배열의 현재 인덱스를 제외하고 나머지 곱의 합으로 업데이트 한다.

Code

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

        for i in range(len(nums)):
            ans[i] *= left
            left *= nums[i]
        
        for i in range(len(nums)-1, -1, -1):
            ans[i] *= right
            right *= nums[i]

        return ans

Complexicity

시간 복잡도

첫번째 반복문에서 주어진 nums의 배열만큼 탐색하고,
두번째 반복문도 마찬가지이다. 각각 O(n)이 소요되므로 총 시간복잡도는 O(n)이다.

공간 복잡도

왼쪽누적곱의 합, 오른쪽 누적곱의 합을 업데이트하기 위해 nums의 길이와 동일한 배열을 생성하므로 공간복잡도는 O(n)이다.

---