파이썬 알고리즘 인터뷰 11번 자신을 제외한 배열의 곱 (리트코드 238번)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

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.

정수 배열 nums에서 자기 자신을 빼고 곱한 값이 담긴 배열을 만들어라.

나누기 연산을 쓰지 않고, 시간 복잡도 O(n)으로 구현하라.

Solution

1차 풀이

from typing import List

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

        for i in range(length - 1):
            prefix.append(prefix[i] * nums[i])
            suffix.append(suffix[i] * nums[length-i-1])

        for i in range(length):
            result.append(prefix[i] * suffix[length-i-1])

        return result

prefix sum array에서 힌트를 얻어서 풀었다.

prefix는 앞에서부터 곱한 값을 하나씩 넣었고, suffix는 뒤에서부터 곱한 값을 하나씩 넣었다.

nums = [a,b,c,d,e]로 예시를 들자면

prefix = [1, a, ab, abc, abcd]

suffix = [1, e, de, cde, bcde]으로 구성했다.

따라서 i일 때 prefix[i] * suffix[length-i-1]를 하면 해당 nums[i]를 제외하고 곱한 값이 나온다.

Reference

https://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/