238. Product of Array Except Self

Problem

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

Follow up:

Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Solution

Problem

요약

• 주어진 배열 nums에서 각 원소 nums[i]를 제외한 나머지 요소들의 곱(product)을 계산하여 새로운 배열 answer를 반환해야 함.
• 나눗셈(division) 사용 금지
• O(N) 시간 복잡도로 해결해야 함.

풀이

나눗셈 없이 해결하거나, 공간 최적화를 통해 푼다.

(1) 기본적인 방법 (O(N) 시간, O(N) 공간)

• 왼쪽 곱(left products) 배열 + 오른쪽 곱(right products) 배열을 활용
• left[i]는 nums[i] 왼쪽의 모든 요소의 곱.
• right[i]는 nums[i] 오른쪽의 모든 요소의 곱.
• 최종 결과는 answer[i] = left[i] * right[i].

(2) 공간 최적화 (O(N) 시간, O(1) 추가 공간)

• left와 right 배열을 별도로 만들 필요 없이, 출력 배열을 활용하여 in-place 계산 가능.
• 두 번의 반복으로 해결 가능:
  왼쪽에서 오른쪽으로 가면서 왼쪽 곱을 계산하여 answer[i]에 저장.
  오른쪽에서 왼쪽으로 가면서 오른쪽 곱을 answer[i]에 곱함.

Constraints

• 2 ≤ nums.length ≤ 10⁵
  • 입력 배열의 크기가 최대 100,000개까지 가능 → O(N²) 불가능, 반드시 O(N) 유지해야 함.
• -30 ≤ nums[i] ≤ 30
  • 값의 범위가 작아서 정수 범위 초과 문제 없음.
• answer[i]는 32-bit 정수 범위 내에서 표현 가능
• 오버플로우 걱정 없음.
• Follow-up 요구사항:
  • O(1)의 추가 공간을 사용하여 해결할 수 있는지 고민해보기.
  • 단, 출력 배열(answer)은 공간 복잡도 계산에서 제외됨.

Code

Time & Space Complexity

연산	복잡도	설명
left_product 계산	O(N)	왼쪽 곱 계산
right_product 곱하기	O(N)	오른쪽 곱 계산
총 시간 복잡도	O(N)	배열을 두 번 순회
추가 공간 복잡도	O(1)	answer 배열

#include <iostream>
#include <vector>

using namespace std;

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> answer(n, 1);  // 결과 배열 초기화

    // Step 1: 왼쪽 곱 계산
    int left_product = 1;
    for (int i = 0; i < n; i++) {
        answer[i] = left_product;
        left_product *= nums[i];  // 현재 값까지 곱해서 왼쪽 곱 갱신
    }

    // Step 2: 오른쪽 곱 계산 및 결과 배열 업데이트
    int right_product = 1;
    for (int i = n - 1; i >= 0; i--) {
        answer[i] *= right_product;
        right_product *= nums[i];  // 현재 값까지 곱해서 오른쪽 곱 갱신
    }

    return answer;
}