자기 자신을 제외한 원소들의 곱 구하기

배열의 각 위치에서 자기 자신을 제외한 나머지 값들의 곱을 구하는 문제입니다.

나눗셈을 사용하지 않고, 왼쪽 누적 곱과 오른쪽 누적 곱을 이용해 해결합니다.

문제

정수로 이루어진 배열 nums가 주어집니다.

새로운 배열 result를 만들 때, result[i]에는 nums[i]를 제외한 나머지 모든 원소의 곱이 들어가야 합니다.

단, 나눗셈은 사용하지 않는다고 가정합니다.

예시 1

입력: [1, 2, 3, 4, 5]
출력: [120, 60, 40, 30, 24]

설명:

0번 위치: 2 x 3 x 4 x 5 = 120
1번 위치: 1 x 3 x 4 x 5 = 60
2번 위치: 1 x 2 x 4 x 5 = 40
3번 위치: 1 x 2 x 3 x 5 = 30
4번 위치: 1 x 2 x 3 x 4 = 24

예시 2

입력: [3, 2, 1]
출력: [2, 3, 6]

설명:

0번 위치: 2 x 1 = 2
1번 위치: 3 x 1 = 3
2번 위치: 3 x 2 = 6

예시 3

입력: [1, 2, 0, 4]
출력: [0, 0, 8, 0]

설명:

0번 위치: 2 x 0 x 4 = 0
1번 위치: 1 x 0 x 4 = 0
2번 위치: 1 x 2 x 4 = 8
3번 위치: 1 x 2 x 0 = 0

처음 떠오르는 생각

가장 단순한 방법은 각 위치마다 자기 자신을 제외하고 전체 배열을 다시 도는 방식입니다.

예를 들어 nums[i]를 기준으로 다시 배열 전체를 돌면서 i가 아닌 값만 곱합니다.

for (let i = 0; i < nums.length; i++) {
  for (let j = 0; j < nums.length; j++) {
    if (i !== j) {
      // nums[j]를 곱한다
    }
  }
}

이 방법은 이해하기 쉽지만, 배열 길이가 커질수록 느려집니다.

배열 길이가 n이면 매번 다시 n번 가까이 돌기 때문에 시간 복잡도는 O(n²)입니다.

왜 나눗셈 풀이를 바로 쓰지 않을까

처음에는 전체 곱을 한 번 구한 뒤, 각 위치에서 자기 자신으로 나누면 된다고 생각하기 쉽습니다.

전체 곱 / 현재 값

이 방식은 겉으로는 간단합니다. 하지만 문제에서 나눗셈을 사용하지 않는다는 조건이 붙는 경우가 많고, 0이 포함되면 처리도 까다로워집니다.

예를 들어 배열에 0이 하나만 있어도 전체 곱이 0이 됩니다. 그 상태에서는 단순 나눗셈 풀이가 곧바로 무너지기 쉽습니다.

그래서 이 문제는 왼쪽 누적 곱과 오른쪽 누적 곱으로 푸는 방식이 더 안정적입니다.

핵심 아이디어

이 문제는 이렇게 나눠서 생각하면 쉽습니다.

result[i] = i 왼쪽에 있는 값들의 곱 x i 오른쪽에 있는 값들의 곱

예를 들어 배열이 아래와 같다고 해보겠습니다.

[1, 2, 3, 4, 5]

인덱스 2의 값은 3입니다.

자기 자신인 3을 제외하면 왼쪽은 [1, 2], 오른쪽은 [4, 5]입니다.

왼쪽 곱: 1 x 2 = 2
오른쪽 곱: 4 x 5 = 20
결과: 2 x 20 = 40

즉, 각 위치마다 왼쪽 곱과 오른쪽 곱을 구하면 됩니다.

이 아이디어의 좋은 점은 현재 값을 직접 나누지 않아도 된다는 것입니다. 즉, 0이 들어 있어도 같은 구조로 처리할 수 있습니다.

풀이 방식

배열을 두 번 순회합니다.

왼쪽에서 오른쪽으로 이동하면서 현재 위치의 왼쪽 곱을 저장합니다.
오른쪽에서 왼쪽으로 이동하면서 현재 위치의 오른쪽 곱을 곱합니다.

처음에는 모든 값을 1로 채운 결과 배열을 만듭니다.

result = [1, 1, 1, 1, 1]

1단계: 왼쪽 곱 저장

nums:   [1, 2, 3, 4, 5]
result: [1, 1, 2, 6, 24]

각 위치에는 자기 자신보다 왼쪽에 있는 값들의 곱이 들어갑니다.

2단계: 오른쪽 곱 반영

오른쪽에서 왼쪽으로 이동하면서 오른쪽 값들의 곱을 곱합니다.

왼쪽 곱:          [1, 1, 2, 6, 24]
오른쪽 곱 반영 후: [120, 60, 40, 30, 24]

0이 들어 있어도 되는 이유

이 풀이가 깔끔한 이유 중 하나는 0이 있어도 별도 분기 없이 동작한다는 점입니다.

예를 들어 [1, 2, 0, 4]를 보면:

왼쪽 누적 곱을 만들 때 0을 만나면 그 뒤쪽 값들은 자연스럽게 0의 영향을 받습니다.
오른쪽 누적 곱을 곱할 때도 같은 방식으로 반영됩니다.

즉, 특정 위치를 제외한 왼쪽과 오른쪽 곱만 계속 쌓아가면 되기 때문에, 0이 있는 경우도 결과가 자연스럽게 계산됩니다.

코드

function productExceptSelf(nums) {
  const result = new Array(nums.length).fill(1);

  let leftProduct = 1;

  for (let i = 0; i < nums.length; i++) {
    result[i] = leftProduct;
    leftProduct *= nums[i];
  }

  let rightProduct = 1;

  for (let i = nums.length - 1; i >= 0; i--) {
    result[i] *= rightProduct;
    rightProduct *= nums[i];
  }

  return result;
}

코드 해설

결과 배열 만들기

const result = new Array(nums.length).fill(1);

입력 배열과 같은 길이의 배열을 만들고, 모든 값을 1로 채웁니다.

곱셈에서 1은 아무 영향을 주지 않는 기본값입니다.

왼쪽 곱 계산

let leftProduct = 1;

for (let i = 0; i < nums.length; i++) {
  result[i] = leftProduct;
  leftProduct *= nums[i];
}

leftProduct는 현재 위치보다 왼쪽에 있는 값들의 곱입니다.

처음 위치에는 왼쪽에 아무 값도 없으므로 1을 넣습니다.

그다음 현재 값을 leftProduct에 곱해서 다음 위치에서 사용할 준비를 합니다.

오른쪽 곱 계산

let rightProduct = 1;

for (let i = nums.length - 1; i >= 0; i--) {
  result[i] *= rightProduct;
  rightProduct *= nums[i];
}

rightProduct는 현재 위치보다 오른쪽에 있는 값들의 곱입니다.

오른쪽 끝에서 시작하면 오른쪽에 아무 값도 없기 때문에 처음 값은 1입니다.

그리고 기존에 저장된 왼쪽 곱에 오른쪽 곱을 곱해 최종 값을 만듭니다.

실수하기 쉬운 부분

이 문제는 구현이 짧은 편이라 오히려 작은 실수를 하기 쉽습니다.

결과 배열을 `0`으로 채우는 실수

const result = new Array(nums.length).fill(0);

이렇게 만들면 뒤에서 아무리 곱해도 값이 살아나지 않습니다. 곱셈의 기본값은 1이어야 합니다.

왼쪽 곱과 오른쪽 곱의 갱신 순서를 바꾸는 실수

result[i] = leftProduct;
leftProduct *= nums[i];

이 순서가 중요합니다. 먼저 저장하고, 그다음 현재 값을 곱해야 자기 자신을 제외한 왼쪽 곱이 됩니다.

공간 복잡도를 헷갈리는 경우

결과 배열 result는 정답으로 반환할 배열입니다. 그래서 보통 추가 공간은 leftProduct, rightProduct 정도만 보고 O(1)로 설명합니다.

실행 예시

console.log(productExceptSelf([1, 2, 3, 4, 5]));
// [120, 60, 40, 30, 24]

console.log(productExceptSelf([3, 2, 1]));
// [2, 3, 6]

console.log(productExceptSelf([1, 2, 0, 4]));
// [0, 0, 8, 0]

복잡도

구분	복잡도
시간 복잡도	O(n)
공간 복잡도	O(1)

결과 배열을 제외하면 추가로 사용하는 값은 leftProduct, rightProduct 정도입니다.

그래서 보통 이 풀이의 추가 공간 복잡도는 O(1)로 봅니다.

정리

이 문제의 핵심은 자기 자신을 제외한 모든 곱을 직접 다시 계산하지 않는 것입니다.

현재 위치를 기준으로 왼쪽 곱과 오른쪽 곱을 나누어 생각하면 나눗셈 없이도 해결할 수 있습니다.

현재 위치의 결과 = 왼쪽 곱 x 오른쪽 곱

단순히 전체 곱을 구하고 나누는 방식은 쉬워 보이지만, 문제 조건에서 나눗셈을 금지하면 사용할 수 없습니다.

그래서 누적 곱을 양쪽에서 한 번씩 계산하는 방식이 더 안정적인 풀이입니다.