LeetCode 238 - Product of Array Except Self

이 문제는 배열의 각 위치마다 자기 자신을 제외한 나머지 원소들의 곱을 구하는 문제다. 난이도는 Medium이고, 나눗셈을 쓰지 않으면서 선형 시간에 풀어야 한다는 조건 때문에 left product와 right product를 따로 누적하는 방식으로 풀었다.

문제 링크 & 설명

문제 링크: 238. Product of Array Except Self
요약: 정수 배열 nums가 주어졌을 때, 각 인덱스마다 자기 자신을 제외한 모든 원소의 곱을 담은 배열을 반환하는 문제.

예를 들어 입력이 이렇게 주어진다고 해보자.

nums = [1, 2, 3, 4]

각 위치의 결과는 자기 자신을 제외한 나머지 값들의 곱이다.

index 0: 2 * 3 * 4 = 24
index 1: 1 * 3 * 4 = 12
index 2: 1 * 2 * 4 = 8
index 3: 1 * 2 * 3 = 6

그래서 결과는 다음과 같다.

[24, 12, 8, 6]

이건 전체 곱을 구한 뒤 현재 원소로 나누면 간단하게 끝나는 문제였지만, 문제 조건에서 나눗셈을 사용할 수 없고, 0이 포함될 때도 나눗셈 방식은 별도 처리가 필요해진다. 그래서 각 위치를 기준으로 왼쪽에 있는 값들의 곱과 오른쪽에 있는 값들의 곱을 따로 구한 뒤, 둘을 곱하는 방식으로 접근했다.

접근 방법

1. 왼쪽 누적 곱 저장하기

자기 자신을 제외한 곱은 현재 위치의 왼쪽 값들의 곱과 오른쪽 값들의 곱으로 나눌 수 있다.

예를 들어 nums = [1, 2, 3, 4]에서 인덱스 2의 값은 3이다. 이때 자기 자신을 제외한 곱은 왼쪽의 1 * 2와 오른쪽의 4를 곱한 값이다.

먼저 answer 배열을 전부 1로 초기화하고, 왼쪽에서 오른쪽으로 순회하면서 각 위치의 왼쪽 누적 곱을 저장한다.

n = len(nums)
answer = [1] * n
acc = 1

for i in range(1, n):
    acc *= nums[i - 1]
    answer[i] = acc

이 루프가 끝나면 answer에는 각 위치의 왼쪽에 있는 값들의 곱이 들어간다.

nums   = [1, 2, 3, 4]
answer = [1, 1, 2, 6]

인덱스 0은 왼쪽에 아무 값도 없으므로 1로 둔다.

2. 오른쪽 누적 곱을 곱해주기

이제 오른쪽에서 왼쪽으로 순회하면서 각 위치의 오른쪽 누적 곱을 구하고, 이미 저장된 왼쪽 누적 곱에 곱해준다.

acc = 1

for i in range(n - 2, -1, -1):
    acc *= nums[i + 1]
    answer[i] *= acc

오른쪽 누적 곱을 별도 배열에 저장하지 않고, acc 변수 하나로 유지하면서 answer에 바로 반영한다. 앞에서 answer에 왼쪽 누적 곱을 넣어두었기 때문에, 두 번째 순회에서는 오른쪽 누적 곱만 곱하면 최종 결과가 된다.

left product  = [1, 1, 2, 6]
right product = [24, 12, 4, 1]
result        = [24, 12, 8, 6]

이 방식은 0이 포함되어도 별도의 분기 없이 동작한다. 각 위치의 결과를 실제로 왼쪽 곱과 오른쪽 곱으로 만들기 때문에, 전체 곱을 나누는 방식처럼 0을 따로 계산할 필요가 없다.

복잡도 분석

시간 복잡도: O(n)
- 배열을 왼쪽에서 한 번, 오른쪽에서 한 번 순회한다. 전체 순회 횟수는 2n이지만 Big-O에서는 O(n)으로 정리한다.
공간 복잡도: O(n)
- 결과를 저장하는 answer 배열이 필요하다. LeetCode 기준으로 출력 배열을 추가 공간에서 제외하면, 별도로 사용하는 값은 acc와 인덱스뿐이므로 extra space는 O(1)로 볼 수 있다.

구현 코드

최종 코드는 answer 배열에 왼쪽 누적 곱을 먼저 저장하고, 두 번째 순회에서 오른쪽 누적 곱을 곱하는 방식이다.

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n

        acc = 1
        for i in range(1, n):
            acc *= nums[i - 1]
            answer[i] = acc

        acc = 1
        for i in range(n - 2, -1, -1):
            acc *= nums[i + 1]
            answer[i] *= acc

        return answer

요약 및 회고

나눗셈을 쓰지 못하는 조건 때문에 전체 곱을 한 번에 계산하는 방식은 사용할 수 없었다. 대신 각 위치를 기준으로 왼쪽 누적 곱과 오른쪽 누적 곱을 따로 계산하면 자기 자신을 제외한 곱을 만들 수 있다.

이번 풀이에서는 answer 배열에 왼쪽 누적 곱을 먼저 저장하고, 오른쪽 누적 곱은 acc 하나로 유지하면서 곱해주는 방식으로 정리했다.