JavaScript에서 현재 숫자보다 작은 요소의 개수 구하기

문제 소개

이번 문제는 숫자 배열을 입력으로 받는 JavaScript 함수를 작성하는 것입니다.

함수는 입력 배열을 기반으로 새로운 배열을 만들어야 하며, 새 배열의 각 요소는 원본 배열에서 해당 위치의 숫자보다 작은 값의 개수를 나타내야 합니다.

예시

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

const arr = [2, 7, 3, 1, 56, 4, 7, 8];

그렇다면 출력 배열은 아래와 같아야 합니다.

const output = [1, 4, 2, 0, 7, 3, 4, 6];

출력 결과를 살펴보면 각 요소가 어떤 의미인지 쉽게 이해할 수 있습니다.

첫 번째 요소 2보다 작은 수는 1 하나뿐이므로 결과는 1입니다.
두 번째 요소 7보다 작은 수는 2, 3, 1, 4의 네 개이므로 결과는 4입니다.
네 번째 요소 1은 배열에서 가장 작은 값이므로 결과는 0입니다.

구현 방법: 이중 반복문 활용

가장 직관적인 풀이 방법은 이중 반복문을 사용하는 것입니다. 바깥쪽 반복문으로 기준이 되는 요소를 하나씩 선택하고, 안쪽 반복문으로 나머지 모든 요소와 비교하여 더 작은 값의 개수를 세면 됩니다.

코드

const arr = [2, 7, 3, 1, 56, 4, 7, 8];

const smallerThanCurrent = (arr = []) => {
  let { length } = arr;
  let res = Array(length).fill(0);

  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length; ++j) {
      // 자기 자신은 제외하고, 기준값보다 작은 경우에만 카운트
      if (i !== j && arr[i] > arr[j]) {
        ++res[i];
      }
    }
  }
  return res;
};

console.log(smallerThanCurrent(arr));

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

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

동작 원리 정리

결과 배열 초기화: 입력 배열과 같은 길이의 배열을 만들고 0으로 채웁니다.
기준 요소 선택: 바깥쪽 반복문(i)으로 비교 대상이 되는 요소를 하나씩 선택합니다.
전체 요소와 비교: 안쪽 반복문(j)으로 배열의 모든 요소를 확인하며, 인덱스가 다르면서(i !== j) 값이 더 작으면(arr[i] > arr[j]) 카운트를 증가시킵니다.
결과 반환: 모든 비교가 끝나면 카운트가 담긴 배열을 반환합니다.

성능 고려 사항

이 풀이는 시간 복잡도가 O(n²)입니다. 배열의 길이가 짧거나 중간 정도라면 충분히 실용적이지만, 데이터가 매우 큰 경우에는 배열을 복사한 뒤 정렬하고 각 값의 순위를 매핑하는 방식(O(n log n))을 고려해볼 수 있습니다. 다만 코드의 단순함과 가독성 측면에서는 위의 이중 반복문 방식이 가장 이해하기 쉬운 접근법입니다.