이번 글에서는 배열을 세트 비트(set bit) 개수를 기준으로 정렬하는 흥미로운 문제를 다뤄보겠습니다. 세트 비트란 숫자를 이진수로 표현했을 때 값이 1인 비트의 개수를 의미합니다. 규칙은 간단합니다. 세트 비트가 더 많은 요소일수록 세트 비트가 적은 요소보다 앞쪽에 배치됩니다.
예를 들어 숫자 12, 15, 7의 이진 표현은 각각 1100, 1111, 0111이며, 세트 비트 개수는 순서대로 2개, 4개, 3개입니다. 따라서 정렬 후 결과는 다음과 같습니다.
1111, 0111, 1100 (15, 7, 12)
문제 해결 접근 방식
정렬을 수행하려면 먼저 각 숫자의 세트 비트 개수를 구해야 합니다. 그다음 C++ STL의 sort 함수를 사용하되, 세트 비트 개수를 비교하는 사용자 정의 비교 함수(compare)를 함께 전달하면 됩니다. 비트 연산만으로 세트 비트를 효율적으로 셀 수 있기 때문에 별도의 변환 과정 없이 간단하게 구현할 수 있습니다.
알고리즘
getSetBitCount(number):
시작
count := 0
number가 0이 아닌 동안 반복:
number AND 1 의 결과가 1이면
count를 1 증가
number를 오른쪽으로 1비트 시프트
count 반환
종료
compare(num1, num2):
시작
count1 = getSetBitCount(num1)
count2 = getSetBitCount(num2)
count1 <= count2이면 false 반환, 아니면 true 반환
종료C++ 구현 예제
#include<iostream>
#include<algorithm>
using namespace std;
int getSetBitCount(int number){
int count = 0;
while(number){
if(number & 1 == 1)
count++;
number = number >> 1; // 숫자를 오른쪽으로 1비트 시프트
}
return count;
}
int compare(int num1, int num2){
int count1 = getSetBitCount(num1);
int count2 = getSetBitCount(num2);
if(count1 <= count2)
return 0;
return 1;
}
int main(){
int data[] = {2, 9, 4, 3, 5, 7, 15, 6, 8};
int n = sizeof(data)/sizeof(data[0]);
sort(data, data + n, compare);
for(int i = 0; i < n; i++){
cout << data[i] << " ";
}
}실행 결과
15 7 9 3 5 6 2 4 8
코드 동작 원리
- getSetBitCount 함수: 비트 AND 연산(
&)과 오른쪽 시프트 연산자(>>)를 이용해 숫자의 가장 오른쪽 비트부터 차례로 검사하며 1의 개수를 셉니다. 숫자가 0이 되면 반복이 종료됩니다. - compare 함수: 두 숫자의 세트 비트 개수를 비교하여, 첫 번째 숫자의 세트 비트가 더 많으면 true를 반환해 해당 요소가 앞쪽에 오도록 합니다. 결과적으로 세트 비트 개수 기준의 내림차순 정렬이 이루어집니다.
- sort 함수: STL의
sort에 위 비교 함수를 전달하면, 세트 비트가 많은 요소부터 배열 앞쪽에 배치됩니다. 같은 세트 비트 개수를 가진 요소들 사이의 상대적 순서는 보장되지 않을 수 있습니다.
이 알고리즘의 전체 시간 복잡도는 정렬 단계가 지배하므로 O(n log n)입니다. 참고로 C++20 이상에서는 std::popcount를 사용하면 세트 비트 개수를 더욱 간결하고 안전하게 구할 수 있습니다.