Leetcode 238. Product of Array Except Self - Python

Leetcode 238 문제 보기

 

문제 이해하기

-30이상 30이하의 수로 이루어진 리스트 nums가 있다.

이때 각 숫자당, 본인을 제외한 나머지 숫자들의 곱을 가지는 리스트를 출력하라.

예를 들어 nums = [1,2,3,4]일 경우, [(2 * 3 * 4), (1 * 3 * 4), (1 * 2 * 4), (1 * 2 * 3)], 즉 [24,12,8,6]를 출력하면된다.

다만 나눗셈을 사용해서는 안되며 O(n) 이내의 시간복잡도를 가져야한다.

 

아이디어 구상

보통의 경우라면, nums의 모든 숫자를 곱한 값에서 각 원소를 나누면 답이 쉽고 빠르게 나올 것이다.

그러나 본 문제에서는 나눗셈을 사용해서는 안된다.

그렇다면 어떻게 해결해야할까?

 

시각화를 통해 생각을 정리해보자. (nums = [1,2,3,4]일 경우를 생각해보자)

 

By Mesotes

예를 들어 숫자 2에 해당하는 결과값을 구하고 싶다.

이때 2 이전까지의 숫자인 1과, 2 이후의 숫자들인 3과 4를 곱해야한다.

즉, 어떤 숫자를 기준으로 그 이전까지의 숫자들과 그 이후 숫자들의 곱이 정답이 된다.

 

때문에, 결과 리스트에 1."이전 숫자들의 곱"을 넣고, 2."이후 숫자들의 곱"을 곱해주면 정답을 얻을 수 있겠다.

이때 양 끝의 숫자는 각각 "이전 숫자"와 "이후 숫자"가 존재하지 않으므로, 이 경우 곱해도 값이 변하지 않는 1을 넣어준다.

 

By Mesotes

 

이 때의 시간복잡도는 어떻게 될까?

리스트 단방향 탐색을 2차례 진행하며 최종 결과를 얻게되므로,

Time Complexity ~ O(n)일 것이다.

 

즉, 문제의 요구조건인 O(n)이내의 시간복잡도를 만족한다.

 

풀이

우선 결과를 담을 리스트 res를 초기화한다.

res = [1] * len(nums)

 

이전 숫자들의 곱을 res에 담는 과정을 진행한다.

prefix = 1
for i in range(len(nums)):
    res[i] = prefix
    prefix *= nums[i]

 

이후 숫자들의 곱을 res에 담는 과정을 진행한다.

여기서 for문을 돌릴 시 수를 감소시키는 방향으로 코드를 작성할 때,

개인적으로 range(n - 1, -1, -1) 등이 아니라 reversed(range(n))를 주로 사용하고 있다.

보다 파이썬다운(pythonic) 방식은 전자이나, 실험 결과 후자가 일반적으로 속도가 더 빠른 듯 하다.

postfix = 1
for i in reversed(range(len(nums))):
    res[i] *= postfix
    postfix *= nums[i]

 

전체 코드는 다음과 같다.

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

 

---

Leetcode 238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/​

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다