JavaScript로 이진 표현의 1 개수를 기준으로 배열 정렬하기

문제 소개

숫자로 이루어진 배열을 입력받아, 각 숫자를 이진수로 변환했을 때 포함된 1의 개수를 기준으로 내림차순 정렬하는 JavaScript 함수를 작성하는 것이 목표입니다. 즉, 이진 표현에서 1이 가장 많은 숫자가 배열 맨 앞에 오도록 재정렬한 새로운 배열을 반환해야 합니다.

접근 방법

이 문제는 두 단계로 나누어 해결할 수 있습니다.

1의 개수 세기: Number.prototype.toString(2)로 숫자를 이진 문자열로 변환한 뒤, 문자열에서 '1'의 개수를 계산합니다.
정렬 수행: Array.prototype.sort()의 비교 함수에서 두 숫자의 1 개수 차이를 반환하면, 1이 많은 숫자부터 앞쪽에 오도록 내림차순 정렬됩니다.

구현 코드

const arr = [5, 78, 11, 128, 124, 68, 6];

// 숫자를 이진 문자열로 변환한 후 1의 개수를 세는 함수
const countOnes = (num) => {
   return num
      .toString(2)
      .split('')
      .filter(bit => bit === '1')
      .length;
};

// 1의 개수를 기준으로 내림차순 정렬하는 함수
const sortByHighBit = (arr = []) => {
   return [...arr].sort((a, b) => countOnes(b) - countOnes(a));
};

console.log(sortByHighBit(arr));

출력 결과

[ 124, 78, 11, 5, 68, 6, 128 ]

코드 설명

countOnes 함수

toString(2)를 호출하면 숫자가 2진법 문자열로 변환됩니다. 예를 들어 78은 "1001110"이 되며, 여기에는 1이 네 개 포함되어 있습니다. split('')으로 한 글자씩 분리한 뒤 filter()로 '1'만 걸러내고 length로 최종 개수를 구합니다.

sortByHighBit 함수

sort()의 비교 함수에서 countOnes(b) - countOnes(a)를 반환합니다. 결과가 양수면 b가 앞으로, 음수면 a가 앞으로 오기 때문에 1의 개수가 많은 숫자가 자연스럽게 앞쪽에 배치됩니다. 스프레드 연산자([...arr])로 복사본을 만들어 정렬하므로 원본 배열은 그대로 유지됩니다.

결과 검증

각 숫자의 이진 표현과 1의 개수는 다음과 같습니다.

124 → 1111100 → 1이 5개
78 → 1001110 → 1이 4개
11 → 1011 → 1이 3개
5 → 101 → 1이 2개
68 → 1000100 → 1이 2개
6 → 110 → 1이 2개
128 → 10000000 → 1이 1개

1의 개수가 같은 숫자(5, 68, 6)는 sort()가 안정 정렬(stable sort)이므로 원래 배열 순서가 유지됩니다.

대안: 비트 연산으로 1의 개수 세기

문자열 변환 없이 비트 연산만으로도 1의 개수를 셀 수 있습니다. n & (n - 1) 연산은 수에서 가장 오른쪽에 있는 1비트를 제거한다는 성질을 활용한 방법입니다.

const countOnes = (num) => {
   let count = 0;
   while (num) {
      num &= num - 1; // 가장 낮은 자리의 1비트 제거
      count++;
   }
   return count;
};

이 방식은 1의 개수만큼만 반복하므로 효율적이며, 대량의 데이터를 처리할 때 특히 유용합니다.