[LeetCode 해석 및 풀이] 238. Product of Array Except Self

LeetCode 문제 해석 및 풀이 방법

 

문제 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.

 

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가 주어지면, answer[i]가 nums[i]을 제외한 배열의 모든 요소를 곱한 값을 가지는 배열 answer를 구하세요.

 

나누기 연산 없이 알고리즘이 O(n)이도록 작성해야 합니다.

 

추가 : 당신은 O(1)의 공간복잡도로 문제를 풀 수 있나요? (output 배열은 포함되지 않습니다.)

 

제한조건

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

 

입출력 예

입력	출력
nums = [1,2,3,4]	[24,12,8,6]
nums = [-1,1,0,-3,3]	[0,0,9,0,0]

 

 

해답 및 해설

파이썬 (Python)

우선 각 요소당 나머지 요소를 반복하며 나머지 요소를 곱해주는 것은 시간복잡도가 O(n^2)이 되므로 답이 되지 않는다. 따라서 다른 방식을 써야하는데, 문제에서도 나와있듯이 prefix와 suffix를 이용한다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        prefix = [1] * length
        suffix = [1] * length

        for i in range(1, length):
            prefix[i] = prefix[i-1] * nums[i-1]

        for i in range(length-2, -1, -1):
            suffix[i] = suffix[i+1] * nums[i+1]
        
        return [p*s for p, s in zip(prefix, suffix)]

prefix에서는 앞에 있는 원소를 전부 곱한 값을 넣고, suffix는 뒤에 있는 원소를 전부 곱한 값을 넣는다. 그 후 답을 제출할 때는 prefix와 suffix을 곱한다. 이렇게 되면 모든 과정에서 시간 복잡도가 O(n)가 된다.

 

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

        prefix_p = 1
        for i in range(length):
            answer[i] = prefix_p
            prefix_p *= nums[i]

        suffix_p = 1
        for i in range(length-1, -1, -1):
            answer[i] *= suffix_p
            suffix_p *= nums[i]
        
        return answer

 

공간 복잡도가 O(1)이 되려면 배열에다가 해당 값을 저장하지 말고, 임시로 값을 저장해준 후 진행해주면 된다.