greentea31's Note

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

풀이 과정

배열을 입력받고, 각 배열의 원소에 대해 자기 자신을 제외한 나머지 원소의 곱의 배열을 구하는 문제이다.

문제를 읽고 나서 바로 드는 생각이라면 배열의 전체 원소를 곱해놓고 저장한 뒤, 각 배열의 원소를 나누면서 저장하는 방법일 텐데 이 방법은 다음과 같은 2가지 문제 때문에 안된다.

1. 배열에 0이 포함되어 있는 경우

    [3, 3, 0, 3, 3]이 입력일 때의 정답은 [0, 0, 81, 0, 0]이어야 하는데 전체 원소의 곱을 구해놓고 각 원소로 나누면 3번째 원소를 처리하기가 곤란해진다. 0 / 0 을 처리할 수가 없기 때문이다.

2. 문제에서 나누기 연산을 금지한다고 조건을 걸었음

    나누기 말고 다른 방법으로 풀어주기를 문제에서 원하고 있다.

DP로 문제를 풀 때 흔히 사용되는 누적합 배열을 만들어서 이 문제를 해결할 수 있다. 이 문제의 경우엔 누적합이 아니라 누적곱이다.

길이가 n+1인 입력이 들어왔을 때, d[i] = 0부터 i-1번째까지의 누적곱, d2[i] = n부터 i+1번째까지의 누적곱이라고 하면, answer[i] = d[i] * d2[i]가 성립한다.

위의 식을 사용해서 문제를 해결하였다. 근데 문제에서 메모리 최적화를 후속 조치로 요구했기에, d[i], d2[i]를 선언하지 않고 출력을 위한 answer 리스트만 선언한 뒤 for문 2번 돌려서 문제를 해결하였다.

소스 코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer = [1 for _ in range(len(nums))]
        product = 1
        for i in range(1, len(nums)):
            product *= nums[i-1]
            answer[i] *= product
        product = 1
        for i in range(len(nums)-2, -1, -1):
            product *= nums[i+1]
            answer[i] *= product
        return answer