LeetCode - 238. Product of Array Except Self

[LeetCode] 238. Product of Array Except Self

LeetCode 238번 문제를 풀어보았다.. Link

Problem

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.

Intuition

시간복잡도가 O(n)이어야 한다는 것과 Division을 이용한 방법으로는 풀 수 없도록 제약조건이 걸려있어 까다로워진 문제

O(n)의 시간복잡도여야 하기에 그때그때 리스트를 슬라이싱해서 값을 알아내면 안되고 적절하게 값을 업데이트해가며 써먹어야한다.

신박한 다른 방법이 있나 찾아봤지만 없어서 가장 정석으로 보이는 Prefix, Postfix를 구하는 방법을 사용하여 풀어보았다.

Approach

1. Answer로 사용될 temp 리스트를 생성한다.
2. prefix는 i번째 숫자를 제외한 왼쪽의 모든 값의 곱으로, 처음에는 1로 초기화한다.
3. temp[i]에 prefix를 대입하고, prefix에 nums[i]를 곱한다. 이러면 prefix는 이제 i번째 숫자를 포함한 왼쪽의 모든 값의 곱이 된다.
4. 3을 i가 len(nums)-1이 될때까지 반복한다. (입력 nums의 모든 포지션에 대해서 반복한다.)
5. postfix는 i번째 숫자를 제외한 오른쪽의 모든 값의 곱으로, 처음에는 1로 초기화한다.
6. temp[i]에 postfix를 대입하고, postfix에 nums[i]를 곱한다. 이러면 postfix는 이제 i번째 숫자를 포함한 오른쪽의 모든 값의 곱이 된다.
7. 6을 i가 len(nums)-1이 될때까지 반복한다. (입력 nums의 모든 포지션에 대해서 반복한다.)
8. temp를 반환한다.

Complexity

• Time complexity:

  Nums의 Length를 n이라고 할 때 \(O(n) + O(n) = O(2n) = O(n)\)이 된다.

• Space complexity: temp를 사용한 것으로 취급한다면 \(O(n)\)인데 문제에서 정답으로 제출되는 리스트는 제외한다고 했으니 \(O(1)\)이라고 할 수 있다.

My Code

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        temp = [1] * len(nums)
        prefix = 1
        for i in range(len(nums)):
            temp[i] = prefix
            prefix *= nums[i]

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

이런 문제가 기업에서 출제하기 좋은 문제라고 생각한다.

LeetCode 문제설명에서는 제약조건이 먼저 주어졌지만, 실제 인터뷰를 한다고 하면 Brute force부터 시작해서 접근했을 것 이다.

중첩 for문을 사용해서 자기 포지션을 제외한 값을 곱한다음 정답용 List에 넣어주면 된다.