238. Product of Array Except Self

문제

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

예시

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

풀이

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        from functools import reduce
        s = [0 for i in range(len(nums))]
        if nums.count(0) == 1:
            z = list(filter(lambda x : x != 0, nums))
            for i in range(len(nums)):
                if nums[i] == 0:
                    s[i] = reduce(lambda x, y: x * y, z)
            return s
        elif nums.count(0) > 1:
            return s
        else:
            s = reduce(lambda x, y: x * y, nums)
            return [int(s / n) for n in nums]

주어진 input 리스트에서 자기 자신을 제외한 원소의 곱을 구하는 문제이다. 처음에는 모든 원소의 곱을 구한 뒤에 자기 자신만을 나눠주면 되는 쉬운 문제라고 생각했지만 0 의 존재때문에 다른 방식으로 접근해야 했다.

(if문) 0 이 하나만 존재할 경우에는, 0 의 위치에만 다른 원소릐 곱을 넣어주면 된다. 나머지는 0 때문에 모두 0 이기 때문이다. 0 이 아닌 다른 원소만을 z 에 할당하였고 0 일 때, z의 원소를 모두 곱해주었다.

(elif문) input 리스트에 0이 2개 이상 존재하게 되면 무조건 output은 0으로 이루어진 리스트가 될 것이다.

(else문) 모든 원소의 곱을 구한 뒤에 차례대로 자기 자신만을 나눠주었다.

결과

18 / 18 test cases passed.
Status: Accepted
Runtime: 120 ms
Memory Usage: 20.5 MB

추가

• functools.reduce(function, iterable[, initializer])

두 인자의 function을 왼쪽에서 오른쪽으로 iterable의 항목에 누적적으로 적용해서, 이터러블을 단일 값으로 줄입니다. 예를 들어, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5])는 ((((1+2)+3)+4)+5)를 계산합니다. 왼쪽 인자 x는 누적값이고 오른쪽 인자 y는 iterable에서 온 갱신 값입니다. 선택적 initializer가 있으면, 계산에서 이터러블의 항목 앞에 배치되고, 이터러블이 비어있을 때 기본값의 역할을 합니다. initializer가 제공되지 않고 iterable에 하나의 항목만 포함되면, 첫 번째 항목이 반환됩니다.

def reduce(function, iterable, initializer=None):
    it = iter(iterable)
    if initializer is None:
        value = next(it)
    else:
        value = initializer
    for element in it:
        value = function(value, element)
    return value

출처 : 파이썬 설명서 주석판, https://python.flowdas.com/library/functools.html

iterable인 리스트나 배열에 대해서 순차적으로 함수를 적용해나가는 연산이다. 설명이 부실해서 map 함수와 헷갈릴 수 있을 것 같다. map 의 경우에는 원소에 독립적으로 함수를 적용해 나가는 연산이고, reduce의 경우에는 원소와 연산한 결과를 다음 원소와의 연산에 다시 사용하는 연산이다.

value = function(value, element)

에서 알 수 있듯이 value가 새로운 element와 연산되면서 계속 업데이트 됨을 알 수 있다.

나중에 기회가 되면 python 표준 라이브러리에 속하는 functools, itertools, collections 등을 알아보아야 겠다.