나눗셈 없이 O(n)으로 — Product of Array Except Self

LeetCode 238. Product of Array Except Self

문제

정수 배열 nums가 주어질 때, answer[i]가 nums[i]를 제외한 나머지 모든 원소의 곱이 되는 배열 answer를 반환한다.

입력: nums = [1, 2, 3, 4]
출력:        [24, 12, 8, 6]

answer[0] = 2*3*4 = 24, answer[1] = 1*3*4 = 12 … 이런 식이다.

제약이 두 개 붙는다. 이게 이 문제의 전부다.

1. O(n) 시간에 풀 것.
2. 나눗셈 연산자를 쓰지 말 것.

가장 먼저 떠오르는 두 가지 (그리고 왜 안 되는지)

나눗셈

전체 곱을 구해두고 각 자리에서 자기 값으로 나누면 한 방이다.

const total = nums.reduce((a, b) => a * b, 1);
return nums.map((n) => total / n); // ← 금지

문제가 나눗셈을 막은 건 단순히 심술이 아니다. 0이 하나라도 있으면 이 방법은 무너진다. nums에 0이 있으면 total이 0이 되고, 0으로 나누면 Infinity·NaN이 튀어나온다. 0이 두 개 이상이면 정답은 전부 0인데, 나눗셈 방식으로는 이 케이스를 별도 분기 없이 처리할 수 없다. 제약이 곧 힌트인 셈이다.

이중 반복

정의 그대로 매 자리마다 나머지를 다 곱한다.

function productExceptSelf(nums) {
  const n = nums.length;
  const answer = new Array(n).fill(1);
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i !== j) answer[i] *= nums[j];
    }
  }
  return answer;
}

동작은 하지만 O(n²)이다. O(n) 제약에 걸린다.

핵심 아이디어: 왼쪽 곱 × 오른쪽 곱

nums[i]를 제외한 곱은 이렇게 쪼갤 수 있다.

answer[i] = (i보다 왼쪽에 있는 모든 값의 곱) × (i보다 오른쪽에 있는 모든 값의 곱)

[1, 2, 3, 4]에서 인덱스 2(값 3)를 보면:

왼쪽 곱 = 1 * 2 = 2
오른쪽 곱 = 4
answer[2] = 2 * 4 = 8  ✅

각 자리의 접두 곱(prefix) 과 접미 곱(suffix) 만 알면, 자기 자신은 애초에 곱셈에 끼지 않으므로 나눗셈이 필요 없다. 그리고 접두/접미 곱은 각각 한 번의 순회로 누적해서 구할 수 있으니 전체가 O(n)이다.

배열 두 개로 (이해용)

먼저 접두 곱 배열 prefix와 접미 곱 배열 suffix를 따로 만들어 본다. prefix[i]는 i 앞까지의 곱, suffix[i]는 i 뒤까지의 곱이다(자기 자신 제외).

function productExceptSelf(nums) {
  const n = nums.length;
  const prefix = new Array(n).fill(1);
  const suffix = new Array(n).fill(1);
 
  // prefix[i] = nums[0..i-1]의 곱
  for (let i = 1; i < n; i++) {
    prefix[i] = prefix[i - 1] * nums[i - 1];
  }
  // suffix[i] = nums[i+1..n-1]의 곱
  for (let i = n - 2; i >= 0; i--) {
    suffix[i] = suffix[i + 1] * nums[i + 1];
  }
 
  return nums.map((_, i) => prefix[i] * suffix[i]);
}

prefix[0]과 suffix[n-1]이 1인 게 포인트다. 양 끝은 한쪽에 아무것도 없으므로 곱의 항등원인 1로 시작한다.

[1, 2, 3, 4]를 대입하면:

prefix = [1, 1, 2,  6]
suffix = [24, 12, 4, 1]
answer = [24, 12, 8,  6]  ✅

출력 배열만 쓰는 O(1) 공간 (최적화)

LeetCode의 follow-up은 "출력 배열을 제외하고 O(1) 추가 공간으로 풀 수 있냐"고 묻는다. prefix, suffix 두 배열을 없애고 결과 배열 하나로 두 번 훑으면 된다.

1. 첫 순회(왼→오): answer[i]에 접두 곱을 채운다.
2. 둘째 순회(오→왼): 변수 하나에 접미 곱을 누적하며 answer[i]에 곱한다.

function productExceptSelf(nums) {
  const n = nums.length;
  const answer = new Array(n).fill(1);
 
  // 1) answer[i] = 왼쪽 곱
  let prefix = 1;
  for (let i = 0; i < n; i++) {
    answer[i] = prefix;
    prefix *= nums[i];
  }
 
  // 2) 오른쪽 곱을 누적하며 곱해준다
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= suffix;
    suffix *= nums[i];
  }
 
  return answer;
}

두 순회 모두 현재 값을 결과에 먼저 반영한 뒤에 누적 변수를 갱신한다(answer[i] = prefix → prefix *= nums[i]). 이 순서 덕분에 자기 자신(nums[i])은 항상 곱에서 빠진다. 순서를 뒤집으면 자기 자신이 곱에 포함돼 버리니 주의.

문제가 막은 나눗셈은 어디에도 없고, 0이 몇 개 있든 분기 없이 그냥 맞는다. 0을 곱하면 자연스럽게 0이 되고, 자기 자신이 0이어도 그 자리엔 나머지 곱만 들어가기 때문이다.

복잡도

* 반환용 answer는 공간 계산에서 제외.

마무리

이 문제의 교훈은 제약을 힌트로 읽는 것이다. "나눗셈 금지"는 곧 "각 자리를 자기 자신 없이 직접 구성하라"는 뜻이었고, 그 답이 접두 곱 × 접미 곱이다. 자기 자신을 애초에 곱셈에 넣지 않으니 나눗셈이 사라지고, 0 처리 같은 예외 분기도 통째로 사라진다.

접두/접미 누적으로 양방향을 훑는 이 패턴은 "자기 자신을 뺀 무언가", "왼쪽·오른쪽을 합쳐야 하는" 부류의 문제(빗물 트래핑, 특정 지점 기준 좌우 최대 등)에서 반복해서 등장한다. 한 번 손에 익혀둘 값어치가 있다.