LeetCode

LeetCode 238 Product of Array Except Self 풀이: 접두사·접미사 곱 누적

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

각 위치에서 자기 자신을 제외한 모든 원소의 곱을 구해야 하며, 나눗셈을 사용할 수 없다. 왼쪽과 오른쪽의 누적 곱을 하나의 결과 배열에 나누어 기록하는 관찰이 필요하므로 Level 2로 판단했다. 0이 포함될 수 있는 조건까지 고려해야 하지만, 구현 자체는 두 번의 선형 순회로 단순하게 유지할 수 있다.

1. 문제 요약

정수 배열 nums가 주어질 때, 각 i에 대해 nums[i]를 제외한 나머지 모든 원소의 곱을 담은 배열을 반환한다. 결과 배열의 순서는 입력 배열과 같아야 한다.

중요한 조건은 다음과 같다.

  • 배열의 길이는 2 이상 10^5 이하이다.
  • 원소는 -30 이상 30 이하의 정수이다.
  • 나눗셈 연산을 사용할 수 없다.
  • 각 결과값은 32비트 정수 범위 안에 들어온다.
  • 결과 배열 자체를 제외한 추가 공간을 O(1)로 사용하는 풀이가 요구된다.

예를 들어 [1, 2, 3, 4]에서 두 번째 원소의 결과는 1 * 3 * 4 = 12다. 각 위치마다 전체 배열을 다시 순회하면 O(n^2)이 되므로, 이미 계산한 방향별 곱을 재사용해야 한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

접두사·접미사 곱 상태

answer[i]를 먼저 i보다 왼쪽에 있는 원소들의 곱으로 채운다. 왼쪽에서 오른쪽으로 순회하면서 현재 위치에 prefix를 기록한 뒤, 현재 원소를 prefix에 곱한다.

그 다음 오른쪽에서 왼쪽으로 순회하면서 suffix를 유지한다. 현재 위치의 answer[i]에 i보다 오른쪽에 있는 원소들의 곱인 suffix를 곱하면, 왼쪽 곱과 오른쪽 곱이 합쳐져 자기 자신을 제외한 전체 곱이 된다.

초기값을 곱셈의 항등원인 1로 두면 첫 위치의 왼쪽 곱과 마지막 위치의 오른쪽 곱도 별도 분기 없이 처리할 수 있다.

접두사와 접미사 곱으로 자기 항목 제외하기

인덱스 i의 정답은 다음 두 부분의 곱으로 나눌 수 있다.

answer[i] = nums[0] * ... * nums[i - 1]
            * nums[i + 1] * ... * nums[n - 1]

결과 배열에 왼쪽 곱을 먼저 저장하면 별도의 prefix 배열이 필요하지 않다. 오른쪽 곱을 뒤에서부터 곱해 주면 결과 배열이 최종값으로 갱신된다. 이 방식은 곱셈만 사용하므로 0이 있어도 자연스럽게 동작한다.

상태 전이와 경계 처리

[1, 2, 3, 4]를 예로 들면 첫 번째 순회가 끝난 결과 배열은 다음과 같다.

왼쪽 곱 기록: [1, 1, 2, 6]

이는 각 위치의 왼쪽 원소 곱이다. 뒤에서부터 suffix를 갱신하며 곱하면 다음과 같이 완성된다.

오른쪽 곱 반영: [24, 12, 8, 6]

현재 원소를 answer[index]에 곱하기 전에 suffix를 먼저 반영해야 한다. 그 뒤에 현재 원소를 suffix에 곱해야 현재 원소가 자신의 결과에 포함되지 않는다. 배열에 0이 하나 있으면 0의 위치에는 나머지 곱이 남고, 다른 위치에는 0이 포함되어 0이 된다. 0이 여러 개면 모든 결과가 0이 된다.

오답 접근과 반례

전체 곱을 구한 뒤 각 원소로 나누는 방법은 간단해 보이지만, 문제에서 나눗셈을 금지하고 0이 있는 입력에서 0으로 나눌 수 없다.

nums = [1, 2, 0, 4]

전체 곱은 0이므로 각 위치의 결과를 전체 곱 // nums[i]로 복원할 수 없다. 0의 위치는 1 * 2 * 4 = 8이어야 하고 다른 위치는 0이어야 하므로, 접두사·접미사 곱 방식처럼 나눗셈에 의존하지 않는 풀이가 필요하다.

각 위치마다 자기 자신을 제외하고 모든 원소를 다시 곱하는 방식도 정답은 구하지만 O(n^2)가 되어 배열 길이 10^5 조건에 적합하지 않다.

시간·공간 복잡도

왼쪽에서 오른쪽으로 한 번, 오른쪽에서 왼쪽으로 한 번 순회하므로 시간 복잡도는 O(n)이다. answer, prefix, suffix 외에 추가로 사용하는 공간은 상수 개이므로, 결과 배열을 제외한 추가 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

첫 번째 순회에서는 answer[index]에 현재 원소 왼쪽의 곱을 기록한다. 두 번째 순회에서는 suffix를 곱해 오른쪽의 곱까지 반영한 뒤, 현재 원소를 suffix에 추가한다.

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

        prefix = 1
        for index, number in enumerate(nums):
            answer[index] = prefix
            prefix *= number

        suffix = 1
        for index in range(len(nums) - 1, -1, -1):
            answer[index] *= suffix
            suffix *= nums[index]

        return answer

answer[index]를 갱신할 때는 현재 원소를 아직 suffix에 곱하지 않은 상태여야 한다. 그래서 answer[index] *= suffix를 먼저 실행하고 suffix *= nums[index]를 실행한다. 또한 answer는 문제에서 허용한 반환 배열이므로, 별도의 오른쪽 곱 배열을 만들지 않는다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 양수 입력과 0이 포함된 입력을 확인할 수 있다.

solver = Solution()
assert solver.productExceptSelf([1, 2, 3, 4]) == [24, 12, 8, 6]
assert solver.productExceptSelf([-1, 1, 0, -3, 3]) == [0, 0, 9, 0, 0]

4. 공식 예제와 추가 검증

작성한 productExceptSelf 함수를 Python으로 실행해 공식 예제와 0, 음수, 최소 길이 조건을 확인했다.

공식 예제

입력 기대 결과 확인 결과
nums = [1,2,3,4] [24,12,8,6] 통과
nums = [-1,1,0,-3,3] [0,0,9,0,0] 통과

추가 검증 1: 최소 길이 배열

입력: nums = [2, 3]
기대 출력: [3, 2]
확인 결과: 통과
검증 목적: 각 위치에서 반대편 원소만 곱하는 최소 길이 입력 확인

추가 검증 2: 0이 두 개 있는 배열

입력: nums = [0, 0]
기대 출력: [0, 0]
확인 결과: 통과
검증 목적: 0이 두 개이면 모든 결과가 0이 되는지 확인

추가 검증 3: 음수와 0이 없는 곱

입력: nums = [-2, 4, -1, 2]
기대 출력: [-8, 4, -16, 8]
확인 결과: 통과
검증 목적: 음수의 개수와 곱셈 부호를 양방향 누적에서 올바르게 처리하는지 확인

추가 검증 4: 음수 두 개가 있는 최소 배열

입력: nums = [5, -2]
기대 출력: [-2, 5]
확인 결과: 통과
검증 목적: 최소 길이 배열에서 음수 부호와 양방향 누적을 확인

5. 다른 풀이 방식 검색 및 비교

왼쪽 곱과 오른쪽 곱을 각각 배열에 저장하면 이해하기 쉽지만 O(n)의 보조 공간이 추가로 필요하다. 이 글에서는 왼쪽 곱을 반환 배열에 덮어 쓰고 오른쪽 곱만 변수로 유지해 문제의 추가 공간 조건을 만족한다.

나눗셈을 허용하는 일반적인 상황이라도 0을 별도로 처리해야 한다. 접두사·접미사 방식은 0의 개수에 따른 분기를 만들지 않고 같은 곱셈 규칙으로 처리할 수 있다는 점도 장점이다.

마무리

Product of Array Except Self은 각 위치의 정답을 왼쪽 곱과 오른쪽 곱으로 분리하는 문제다. 결과 배열에 접두사 곱을 기록한 뒤 뒤에서부터 접미사 곱을 곱하면, 나눗셈 없이 O(n) 시간과 결과 배열을 제외한 O(1) 추가 공간으로 해결할 수 있다. 현재 원소를 접미사 곱에 더하는 순서를 결과 반영 뒤로 미루는 것이 핵심 구현 포인트다.

#수학#LeetCode#난이도 2