leetcode 238. Product of Array Except Self 리트코드 238. 자신을 제외한 배열의 곱

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

 

문제

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

Product of Array Except Self - LeetCode

 

입력 : 정수로 된 리스트

출력 : 정수로 된 리스트

 

문제 요약 : 리스트에서 자기 빼고 나머지 원소를 다 곱해서 그 자리에 넣는다.

유의 사항 :

1. 주어진 리스트와 크기가 같은 리스트를 출력하고, i의 자리에 i번째 원소를 제외한 나머지 원소들을 다 곱해서 넣으니까 반복문이 최소 1회는 나와야 한다.

2. 합이 0이 되는 원소 3개가 담긴 리스트들의 리스트로 제출하는데, 정렬이 되어 있어야 하고, 똑같은 결과가 반복해서 나오면 안된다.

3. 복잡도 O(n) 또는 O(1)로 해결해야 한다.

생각 과정

솔직히 혼자서 생각해서 시도한 방법으로는 runtime error가 계속 발생했다.

그래서 leetcode 에 올려진 다른 사람의 풀이방법을 참고했다.

가장 큰 차별점은

for 반복을 도는데, 나는 계속 idx = 2이면 left[0]*left[1]와 right[3]을 같이 처리해서 answer[2]에 넣으려고 했다는 점이다. 그러면 left는 2번의 반복, right는 1번을 해야하니 횟수가 맞지 않았다.

그 풀이법에 따르면 

for idx 2이면 left는 left[0]*left[1]까지 해서 answer[2]에 곱해놓고,

                     right는 right[-1]*right[-2]까지 2번 곱한거니까 answer[1], 즉 answer[-3]에 곱해놓는다.

 

이렇게 하기 위해서 미리 1로 채워진 answer 리스트를 만들어 놓는다.

 

풀이

 

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = [1 for _ in nums]
        left = 1
        right = 1

        for i in range(len(nums)):
            ans[i] *= left
            ans[-1-i] *= right
            left *= nums[i]
            right *= nums[-1-i]
        return ans