JavaScript로 배열의 각 숫자보다 작은 요소 개수 구하기

문제 소개

숫자 배열을 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 원본 배열의 각 요소마다 자신보다 작은 숫자가 몇 개 있는지를 세어, 그 결과를 새로운 숫자 배열로 반환해야 합니다.

예시

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

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

그렇다면 기대하는 출력 결과는 다음과 같습니다.

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

결과를 하나씩 해석해 보면 다음과 같습니다.

• 3보다 작은 수는 1, 2 → 총 2개
• 5보다 작은 수는 3, 4, 1, 2 → 총 4개
• 4보다 작은 수는 3, 1, 2 → 총 3개
• 1보다 작은 수는 없음 → 총 0개
• 2보다 작은 수는 1 → 총 1개

구현 코드

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

코드 설명

• 바깥쪽 for 루프는 배열의 각 요소를 하나씩 순회합니다.
• 안쪽 while 루프는 현재 요소를 배열의 모든 요소와 비교하여, 현재 요소보다 작은 값이 발견될 때마다 count를 1씩 증가시킵니다.
• 각 요소에 대한 비교가 끝나면 그 결과인 count 값을 결과 배열 res에 저장합니다.

루프가 두 겹으로 중첩되어 있기 때문에 이 방법의 시간 복잡도는 O(n²)입니다.

실행 결과

코드를 실행하면 콘솔에 다음과 같이 출력됩니다.

[2, 4, 3, 0, 1]

정렬을 활용한 더 효율적인 방법

배열을 오름차순으로 정렬한 뒤 각 값이 처음 등장하는 위치(인덱스)를 찾으면, 그 인덱스가 곧 해당 값보다 작은 원소의 개수가 됩니다. 이 방법은 시간 복잡도가 O(n log n)으로 더 효율적입니다.

const smallerNumbersThanCurrent = (arr = []) => {
   const sorted = [...arr].sort((a, b) => a - b);
   return arr.map(num => sorted.indexOf(num));
};
console.log(smallerNumbersThanCurrent([3, 5, 4, 1, 2])); // [2, 4, 3, 0, 1]