leetcode 238 (medium)

문제

https://leetcode.com/problems/product-of-array-except-self/

풀이

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        arr = []

        p = 1
        arr.append(p)
        for i in range(len(nums)-1):
            p = p * nums[i]
            arr.append(p)
            
        p = 1
        
        for i in range(len(nums)-1, -1 ,-1):
            arr[i] *= p
            p *= nums[i]
            
        return arr

간단하면서도 어려운 문제였다.

사실 못풀겠어서 해설을 봤는데 이해가 안가서 한참 찾아봤다.

아이디어는 이렇다.

[a,b,c,d,e] 요렇게 5개가 있다고 가정하면

[bcde, acde, abde, abce, abcd]
요런식으로 각 인덱스만 빠진 배열을 만들어내면 되는것이다.

이걸 최적으로 만들어내기 위해서는

for문을 돌면서 자기 자신 바로 왼쪽까지만 곱한걸 구한다.

[1, a, ab, abc, abcd]
그러면 요렇게 될것이다.

이상태에서 같은방법으로 오른쪽부터 왼쪽으로 이동하며 자기자신 바로 오른쪽까지만 곱한걸 구한다.
[bcde,cde,de,e,1]

요렇게 될 것이다. 그러면 이 두개를 곱하면
최종적으로
[bcde, acde, abde, abce, abcd] 요런게 완정된다는 아이디어이다.

for문을 왼쪽부터 한번 오른쪽부터 한번 총 2번 돌면 완성 할 수 있다.

결과