JavaScript로 배열에서 자신보다 뒤에 있는 더 작은 수의 개수 세기

문제 정의

숫자로 이루어진 배열을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 입력 배열을 기반으로 새로운 배열을 생성해 반환해야 합니다. 이때 새 배열의 각 요소는, 원본 배열에서 해당 위치의 요소보다 오른쪽(뒤)에 있으면서 값이 더 작은 요소들의 개수여야 합니다.

예를 들어, 함수에 다음과 같은 배열이 입력된다고 가정해 보겠습니다.

const arr = [4, 7, 1, 4, 7, 5, 3, 8, 9];

그렇다면 출력은 다음과 같아야 합니다.

const output = [2, 4, 0, 1, 2, 1, 0, 0, 0];

출력 결과 해설

• 첫 번째 요소 4의 오른쪽에는 1과 3, 총 2개의 더 작은 수가 있습니다.
• 두 번째 요소 7의 오른쪽에는 1, 4, 5, 3, 총 4개의 더 작은 수가 있습니다.
• 세 번째 요소 1보다 작은 수는 없으므로 0개입니다.
• 마지막 요소 9의 오른쪽에는 어떤 수도 없으므로 역시 0개입니다.

구현 코드

이 문제를 해결하는 코드는 다음과 같습니다.

const arr = [4, 7, 1, 4, 7, 5, 3, 8, 9];

// num보다 작은 요소의 개수를 세는 헬퍼 함수
const countSmaller = (array = [], num) => array.reduce((acc, val) => {
    if (val < num) {
        acc++;
    };
    return acc;
}, 0);

const smallerArray = (arr = []) => {
    const res = [];
    for (let i = 0; i < arr.length; i++) {
        const el = arr[i];
        // 현재 요소부터 배열 끝까지만 잘라서 비교
        res[i] = countSmaller(arr.slice(i, arr.length), el);
    };
    return res;
};

console.log(smallerArray(arr));

실행 결과

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

[ 2, 4, 0, 1, 2, 1, 0, 0, 0 ]

코드 동작 방식

이 코드의 핵심 로직은 다음과 같이 요약할 수 있습니다.

1. countSmaller 함수는 reduce() 메서드를 활용해 주어진 배열 안에서 num보다 작은 값의 개수를 셉니다.
2. smallerArray 함수는 반복문을 돌며 각 요소에 대해, 해당 요소부터 배열 끝까지의 부분 배열(arr.slice(i))만 대상으로 더 작은 수의 개수를 계산합니다.
3. 이렇게 계산된 개수들을 순서대로 새 배열 res에 담아 최종적으로 반환합니다.

참고로 이 방식은 각 요소마다 나머지 부분 배열을 모두 훑어야 하므로 시간 복잡도는 O(n²)입니다. 배열의 크기가 매우 큰 경우에는 병합 정렬(Merge Sort)이나 이진 탐색 트리(BST)를 활용한 O(n log n) 접근법을 고려하는 것이 좋습니다.