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

정수 배열을 유일한 인자로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 각 정수를 이진수 표현에서 1의 개수를 기준으로 오름차순 정렬해야 합니다. 만약 두 개 이상의 숫자가 이진수에서 1의 개수가 같다면, 그 숫자들은 실제 값(크기) 기준으로 오름차순 정렬되어야 합니다.

문제 예시

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

const arr = [34, 37, 23, 89, 12, 31, 23, 89];

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

• 34 → 100010 → 1의 개수: 2개
• 12 → 1100 → 1의 개수: 2개
• 37 → 100101 → 1의 개수: 3개
• 23 → 10111 → 1의 개수: 4개
• 89 → 1011001 → 1의 개수: 4개
• 31 → 11111 → 1의 개수: 5개

따라서 최종 출력 배열은 다음과 같습니다.

const output = [34, 12, 37, 23, 89, 23, 89, 31];

구현 방법

풀이 접근은 다음과 같습니다.

1. 주어진 숫자를 이진수 문자열로 변환합니다.
2. 변환된 문자열에서 '1'의 개수를 세는 헬퍼 함수를 작성합니다.
3. 배열의 sort() 메서드에 비교 함수를 전달하여 1의 개수를 기준으로 정렬합니다.

다음은 전체 코드입니다.

const arr = [34, 37, 23, 89, 12, 31, 23, 89];

const sortByBinary = (arr = []) => {
    // 이진수 문자열에서 1의 개수를 계산하는 헬퍼 함수
    const calculateOne = (str = '') => {
        let res = 0;
        for(let i = 0; i < str.length; i++){
            if(str[i] === '1'){
                res++;
            };
        };
        return res;
    }
    // 1의 개수를 비교하는 정렬 함수
    const sorter = (a, b) => {
        const firstCount = calculateOne((a >>> 0).toString(2));
        const secondCount = calculateOne((b >>> 0).toString(2));
        return firstCount - secondCount;
    };
    arr.sort(sorter);
};

sortByBinary(arr);
console.log(arr);

실행 결과

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

[
    34, 12, 37, 23,
    89, 23, 89, 31
]

코드 설명

(a >>> 0)은 부호 없는 32비트 정수로 변환하는 연산으로, 음수가 포함된 경우에도 안전하게 이진수 변환이 가능하도록 합니다. 이후 toString(2)로 이진수 문자열을 얻고, calculateOne 함수로 1의 개수를 셉니다.

비교 함수 sorter는 두 숫자의 1의 개수 차이를 반환하므로, JavaScript의 Array.prototype.sort()가 자동으로 오름차순 정렬을 수행합니다. 1의 개수가 동일한 경우에는 원래 배열의 순서가 유지되며, 값 기준 정렬이 필요하다면 비교 함수에 a - b 조건을 추가로 반영할 수 있습니다.