자신을 제외한 배열의 곱 문제

 

이 문제는 자신의 배열위치 인덱스가 자신을 제외한 원소들의 곱으로 이뤄진 것으로 바꾸는 문제이다. 

 

예제 1번의 인덱스 0 에 1은 자기자신을 제외한 나머지의 곱인 2*3*4=24 로 바꾸는 것이다.

 

이는 모든 원소들의 곱을 구하고 각 인덱스의 값으로 나눈 값을 취하면 바로 구할 수 있다. 하지만 예제 2번과 같이 만약에 0이 존재한다면, 0으로 나눠야하는 zero division error 가 발생한다.

 

아래의 코드는 그리디하게 구현한 것이다. 문제의 설명대로 인덱스 값을 제외한 나머지 원소들의 곱을 해당 인덱스의 값으로 바꿔주는데 충실한 것이다.

 sp 라는 함수에서는 리스트내의 원소들의 곱을 리턴하는 함수 값이다. 그래서 아래의 for 문을 활용해서 처음 주어진 nums 의 원소들의 인덱스를 하나씩 뺀 나머지들의 product 를 구하여 result 를 만든다. 하지만 이 방법은 time limit exceeded 된다.

    def productExceptSelf(self, nums: List[int]) -> List[int]:

        def sp(nums):
            result = nums.pop()
            while nums:
                result *= nums.pop()
            return result
        
        tmp = nums.copy()
        result = []
        for i in range(len(tmp)):
            result.append(sp(tmp[:i] + tmp[i+1:]))

        return result

 

결국 리스트에서 해당 인덱스의 좌우에 있는 값들의 곱을 구하는 문제로 생각해보면, 나를 기준으로 왼쪽에 있는 원소들의 곱과 오른쪽에 있는 원소들의 곱이 새로운 나가 된다.

 

나를 기준으로 왼쪽 혹은 오른쪽에 값이 없는 경우는 1로 두어서 구한다면 아래와 같이 생각할 수 있다.

 

위의 생각을 구현한 코드는 아래와 같다. 굳이 right 리스트를 만들지 않고 left 를 재활용해서 left의 값을 right 원소와 곱해나가는 식으로 한다면 공간복잡도 O(1) 에 풀이도 가능하다. 

    def productExceptSelf(self, nums: List[int]) -> List[int]:

        left = []
        right = []

        p=1
        for i in range(len(nums)):
            left.append(p)
            p *= nums[i]

        p=1
        rnums = nums[::-1]
        for i in range(len(nums)):
            right.append(p)
            p *= rnums[i]
        right = right[::-1]

        return [a*b for a,b in zip(left, right)]