C++로 배열에서 두 요소의 세트 비트 개수가 같은 쌍 개수 구하기

정수형 요소로 이루어진 배열이 주어졌을 때, 배열의 요소들로 만들 수 있는 모든 쌍(pair)을 구성하고 각 쌍에 속한 두 요소의 세트 비트(set bit) 개수를 계산하여, 두 요소의 세트 비트 수가 서로 같은 쌍이 몇 개인지 확인하는 것이 이번 문제의 목표입니다.

여기서 세트 비트란 이진수에서 1로 표현되는 비트를 의미합니다. 정수 값을 이진수로 변환하면 0과 1의 조합으로 나타나는데, 컴퓨터 용어에서 이때의 숫자 1을 세트 비트라고 부릅니다.

예제 1

입력

int arr[] = {6, 5, 1, 3, 7}

출력

두 요소의 세트 비트 개수가 같은 쌍의 개수: 3

설명

주어진 배열로 만들 수 있는 쌍은 다음과 같습니다.
(6, 5): 6 → 세트 비트 2개, 5 → 세트 비트 2개 (유효한 쌍)
(6, 1): 6 → 2개, 1 → 1개 (유효하지 않음)
(6, 3): 6 → 2개, 3 → 2개 (유효한 쌍)
(6, 7): 6 → 2개, 7 → 3개 (유효하지 않음)
(5, 1): 5 → 2개, 1 → 1개 (유효하지 않음)
(5, 3): 5 → 2개, 3 → 2개 (유효한 쌍)
(5, 7): 5 → 2개, 7 → 3개 (유효하지 않음)
(1, 3): 1 → 1개, 3 → 2개 (유효하지 않음)
(1, 7): 1 → 1개, 7 → 3개 (유효하지 않음)
(3, 7): 3 → 2개, 7 → 3개 (유효하지 않음)
따라서 세트 비트 개수가 같은 유효한 쌍은 총 3개이며,
(6, 5), (6, 3), (5, 3)입니다.

예제 2

입력

int arr[] = {4, 6, 3, 2}

출력

두 요소의 세트 비트 개수가 같은 쌍의 개수: 2

설명

주어진 배열로 만들 수 있는 쌍은 다음과 같습니다.
(4, 6): 4 → 세트 비트 1개, 6 → 세트 비트 2개 (유효하지 않음)
(4, 3): 4 → 1개, 3 → 2개 (유효하지 않음)
(4, 2): 4 → 1개, 2 → 1개 (유효한 쌍)
(6, 3): 6 → 2개, 3 → 2개 (유효한 쌍)
(6, 2): 6 → 2개, 2 → 1개 (유효하지 않음)
(3, 2): 3 → 2개, 2 → 1개 (유효하지 않음)
따라서 세트 비트 개수가 같은 유효한 쌍은 총 2개이며,
(4, 2)와 (6, 3)입니다.

문제 해결 접근 방식

정수 요소로 이루어진 배열을 입력받고, 배열의 크기를 계산한 뒤 데이터를 함수에 전달합니다.
세트 비트 개수가 같은 쌍의 개수를 저장할 임시 변수 count를 선언합니다.
i를 0부터 배열 크기까지 반복하는 FOR 루프를 시작합니다.
루프 내부에서 j를 i + 1부터 배열 크기까지 반복하는 또 다른 FOR 루프를 시작합니다.
루프 내부에서 __builtin_popcount(element) 함수를 호출하여 정수의 전체 세트 비트 개수를 반환받고, 이를 쌍의 첫 번째 요소(first)와 두 번째 요소(second)에 저장합니다.
쌍의 첫 번째 요소와 두 번째 요소의 세트 비트 개수가 같다면 count를 1 증가시킵니다.
모든 반복이 끝나면 count를 반환합니다.
결과를 출력합니다.

참고로 __builtin_popcount()는 GCC 컴파일러에서 제공하는 내장 함수로, 정수의 이진 표현에서 1의 개수(세트 비트 수)를 빠르게 계산해 줍니다.

예제 코드

#include <iostream>
using namespace std;
int pair_setBit(int arr[], int size){
    int count = 0;
    for(int i = 0 ;i <size ; i++){
        for(int j = i+1; j<size; j++){
            int first = __builtin_popcount(arr[i]);
            int second = __builtin_popcount(arr[j]);
            if(first == second){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {6, 5, 1, 3, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"두 요소의 세트 비트 개수가 같은 쌍의 개수: "<<pair_setBit(arr, size);
    return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

두 요소의 세트 비트 개수가 같은 쌍의 개수: 3

시간 복잡도

위 알고리즘은 배열의 모든 요소 쌍을 두 번 중첩된 루프로 검사하므로 시간 복잡도는 O(n²)입니다. 배열의 크기가 매우 큰 경우에는 각 요소의 세트 비트 개수를 미리 계산하여 그룹화한 뒤 조합 공식을 적용하는 방식으로 최적화할 수 있습니다.