[Prefix Sum 문제] LEETCODE.238 Product of Array Except Self

문제풀이

이번 문제는 구간 합 문제 유형이다. 크게 Prefix 결과(선택된 index 이전 결과)와 PostFix(선택된 index 이후 결과의 값)을 활용한다.
1. 보조 리스트 a(Prefix 배열)와 b(Postfix 배열)를 생성하고, a는 각 요소의 왼쪽 요소들의 곱, b는 각 요소의 오른쪽 요소들의 곱을 저장함.
2. a 리스트를 왼쪽에서 오른쪽으로 순회하며 각 요소를 자신의 왼쪽 요소들의 곱으로 설정함.
3. b 리스트를 오른쪽에서 왼쪽으로 순회하며 각 요소를 자신의 오른쪽 요소들의 곱으로 설정함.
4. a와 b 리스트를 병렬로 순회하며 각 위치의 왼쪽과 오른쪽 부분의 곱을 계산하고, 그 결과를 리스트로 반환함. 이렇게 하면 최종적으로 리스트 내의 모든 요소를 제외한 나머지 요소들의 곱이 계산되어 반환함

코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        a=[1]*len(nums)
        a[1]=nums[0]
        b=[1]*len(nums)
        b[-2]=nums[-1]
        for i in range(2,len(nums)):
            a[i]=a[i-1]*nums[i-1]
        
        for i in range(len(nums)-3,-1,-1):
            b[i]=b[i+1]*nums[i+1]
        return [a * b for a,b in zip(a,b)]

Lookback

1. Zip 함수를 통해 한 줄 라인으로 배열 간의 연산 결과를 Return 할 수 있다는 점을 활용해보는 것도 좋을 듯하다.