✓[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.

 

Constraints:

  ▷ 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.

 

Example:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

 

 처음에는 주어진 배열의 길이만큼 순회하면서 매번 배열을 복사하고, 해당 위치의 값을 제거하고 production 함수를 이용해서 결과 배열에 넣을려고 시도했다. 심지어 테스트 케이스도 통과했지만.. 제출을 하면 시간 초과가 났다..

 

from math import prod

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        answer = []
        
        for i in nums:
            temp = nums.copy()
            temp.remove(i)
            answer.append(prod(temp))
        
        return answer

 

 그래서 답지를 보고 문제를 풀어보려 했지만.. 막 이해가 되지 않았다.. 유튜브 해설 강의도 찾아보았지만 그냥 답지를 읽어주는 느낌? 그러다가 리트코드 문제 해설을 너무 잘하는 유튜버를 찾고.. 한 번에 이해하고 원래 갖고있는 책의 해설보다 더 나은 풀이법도 제시해주었다. 천상계 풀이는 이런 것인가 싶었다!

 

 나누기 연산자를 쓰면 안되고 O(n)이라는 조건이 있었다. 정답은 내 위치 앞에 모든 값을 곱하고 뒤의 모든 값을 곱한 뒤, 그 두 값을 곱한 것이니 이를 활용하자는 것이다. prefix배열에서는 input의 좌측에서부터 값을 하나씩 곱해서 배열에 넣어두고, postfix는 input의 우측에서부터 값을 하나씩 곱해 배열에 넣어둔다. 그 다음 result 값을 구하기 위해, prefix에서 한 자리 앞에 값을 빼고 postfix에선 한자리 뒤에 값을 빼서 곱한 값을 result 값을 취해준다. 여기서 out range의 default 값은 1이다. 근데 이렇게 하면 prefix와 post fix 배열의 메모리 공간이 낭비되니, prefix와 postfix 변수만 한 개씩 설정해서 result배열에 바로 연산하자는 것이다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        # assign result array's element with 1
        res = [1] * (len(nums))
        
        # compute prefix job
        prefix = 1
        for i in range(len(nums)):
            res[i] = prefix
            prefix *= nums[i]
        
        # compute postfix job
        postfix = 1
        for i in range(len(nums)-1, -1, -1):
            res[i] *= postfix
            postfix *= nums[i]
        
        return res