JavaScript로 각 요소보다 작은 오른쪽 요소의 개수 배열 구성하기

문제 소개

숫자 배열을 입력받는 JavaScript 함수를 작성해야 합니다. 이 함수는 입력 배열을 기반으로 새로운 출력 배열을 구성한 뒤 반환하는 역할을 합니다.

출력 배열의 각 요소에는, 원본 배열에서 해당 요소의 오른쪽에 위치하면서 그 값보다 작은 숫자의 개수가 들어가야 합니다.

예제

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

const arr = [6, 2, 8, 5, 1, 3];

첫 번째 요소 6의 오른쪽에는 2, 5, 1, 3이라는 네 개의 더 작은 숫자가 있으므로 출력 배열의 첫 번째 값은 4가 됩니다. 같은 방식으로 모든 요소를 검사하면 최종 결과는 다음과 같습니다.

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

풀이 코드

가장 직관적인 방법은 중첩 반복문을 사용하는 것입니다. 바깥쪽 반복문으로 기준 요소를 하나씩 선택하고, 안쪽 반복문으로 그 오른쪽에 있는 요소들을 모두 확인하며 더 작은 값의 개수를 셉니다.

const arr = [6, 2, 8, 5, 1, 3];
const buildSmallerArray = (arr = []) => {
    let count;
    let base;
    const res = [];
    for (let i = 0; i < arr.length; i++) {
        base = arr[i];
        count = 0;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < base) count++;
        };
        res.push(count);
    };
    return res;
};
console.log(buildSmallerArray(arr));

실행 결과

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

코드 동작 원리

이 알고리즘의 동작 과정을 단계별로 살펴보면 다음과 같습니다.

먼저 결과를 저장할 빈 배열 res를 준비합니다. 바깥쪽 반복문은 인덱스 i를 기준으로 배열의 각 요소를 차례대로 선택하며, 선택된 값을 base 변수에 저장합니다. 매번 새로운 기준 요소를 검사하기 전에 카운트 변수 count를 0으로 초기화합니다.

안쪽 반복문은 j = i + 1부터 시작하여 기준 요소의 오른쪽에 있는 모든 요소를 확인합니다. 만약 arr[j]가 base보다 작다면 count를 1 증가시킵니다. 안쪽 반복문이 끝나면 누적된 count 값을 res 배열에 추가(push)합니다.

모든 요소에 대한 검사가 완료되면 res 배열을 반환합니다. 마지막 요소부터는 오른쪽에 비교 대상이 없으므로 항상 0이 기록됩니다.

시간 복잡도

이 풀이는 두 겹의 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. 배열의 크기가 크지 않다면 충분히 실용적이지만, 성능이 중요한 상황에서는 세그먼트 트리나 병합 정렬 기반의 접근 방식을 활용하면 O(n log n)까지 개선할 수 있습니다.