JavaScript로 각 요소별 곱 배열 만들기 — O(n) 풀이

문제 소개

숫자로 이루어진 배열을 입력받아, 각 위치의 값이 자기 자신을 제외한 나머지 모든 요소의 곱이 되는 새로운 배열을 구성하는 JavaScript 함수를 작성해야 합니다. 즉, 배열 전체의 곱을 구한 뒤 각 요소로 나누면 원하는 결과를 얻을 수 있습니다.

예를 들어 다음과 같은 입력 배열이 주어졌다고 가정해 보겠습니다.

const arr = [1, 2, 3, 4, 5];

전체 곱은 1 × 2 × 3 × 4 × 5 = 120입니다. 따라서 각 위치의 출력값은 120을 해당 요소로 나눈 값이 되며, 결과 배열은 다음과 같습니다.

const output = [120, 60, 40, 30, 24];

이 문제는 선형 시간(O(n))과 상수 공간(결과 배열 생성에 필요한 공간은 제외) 안에서 해결해야 한다는 조건이 있습니다.

접근 방법

가장 직관적인 해결 방법은 다음 두 단계로 구성됩니다.

1. reduce() 메서드를 사용해 배열 전체의 곱을 한 번에 계산합니다.
2. 배열을 순회하면서 전체 곱을 각 요소로 나눈 값을 결과 배열에 차례대로 저장합니다.

두 단계 모두 배열을 한 번씩만 순회하므로 전체 시간 복잡도는 O(n)이며, 추가로 사용되는 변수는 곱값 하나뿐이므로 공간 복잡도 조건도 충족합니다.

구현 코드

다음은 위 접근 방식을 구현한 코드입니다.

const arr = [1, 2, 3, 4, 5];
const exclusiveProduct = (arr = []) => {
    // O(n) 시간 복잡도 — 배열 전체의 곱 계산
    const product = arr.reduce((acc, val) => acc * val);
    const res = [];
    // O(n) 시간 복잡도 — 각 요소별 몫 계산
    for(let i = 0; i < arr.length; i++){
        const el = arr[i];
        res[i] = product / el;
    };
    return res;
};
console.log(exclusiveProduct(arr));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

[120, 60, 40, 30, 24]

참고: 예외 상황 처리

위 방법은 나눗셈을 사용하기 때문에 배열에 0이 포함된 경우에는 올바른 결과를 얻을 수 없습니다. 이런 경우에는 왼쪽 누적 곱(prefix product)과 오른쪽 누적 곱(suffix product)을 활용하는 방식으로 대체할 수 있으며, 이 역시 O(n) 시간 복잡도로 동작합니다. 실무에서는 입력 데이터에 0이 존재할 가능성을 항상 고려하여 적절한 방식을 선택하는 것이 좋습니다.