C++로 세트 비트 개수가 같은 숫자들의 최대 합 구하기

문제 설명

N개의 숫자로 이루어진 배열이 주어졌을 때, 세트 비트(set bit, 값이 1인 비트)의 개수가 서로 같은 숫자들끼리 묶어 합산했을 때 얻을 수 있는 최대 합을 찾는 것이 이번 문제의 목표입니다.

예시

입력 배열이 {2, 5, 8, 9, 10, 7}일 때, 각 숫자의 세트 비트 개수는 다음과 같습니다.

• 2 → 세트 비트 1개
• 5 → 세트 비트 2개
• 8 → 세트 비트 1개
• 9 → 세트 비트 2개
• 10 → 세트 비트 2개
• 7 → 세트 비트 3개

여기서 세트 비트가 2개인 숫자들은 5, 9, 10이며, 이들의 합은 5 + 9 + 10 = 24입니다. 다른 그룹(세트 비트 1개: 2+8=10, 세트 비트 3개: 7)보다 크므로 정답은 24가 됩니다.

알고리즘

1. 배열을 순회하면서 각 요소의 세트 비트 개수를 계산합니다.
2. 숫자가 최대 32개의 세트 비트를 가질 수 있다고 가정하고, 크기 32의 합계 배열을 초기화합니다.
3. 배열을 다시 순회하면서 각 요소를 자신의 세트 비트 개수에 해당하는 인덱스 위치에 누적합니다.
4. 합계 배열을 순회하며 최댓값을 찾아 반환합니다.

C++ 구현

#include <bits/stdc++.h>
using namespace std;

// 세트 비트 개수를 계산하는 함수 (브라이언 커니핸 알고리즘)
int bitCount(int n){
    int count = 0;
    while (n) {
        count++;
        n = n & (n - 1);
    }
    return count;
}

// 같은 세트 비트 개수를 가진 숫자들의 최대 합을 구하는 함수
int maxSum(int arr[], int n){
    int bits[n];
    for (int i = 0; i < n; i++) {
        bits[i] = bitCount(arr[i]);
    }

    // 세트 비트 개수별 합계를 저장할 배열 (최대 32비트)
    int sum[32] = { 0 };
    for (int i = 0; i < n; i++) {
        sum[bits[i]] += arr[i];
    }

    // 그룹별 합계 중 최댓값 찾기
    int maximum = 0;
    for (int i = 0; i < 32; i++) {
        maximum = max(sum[i], maximum);
    }
    return maximum;
}

int main(){
    int arr[] = {2, 5, 8, 9, 10, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum sum = " << maxSum(arr, n) << endl;
    return 0;
}

출력 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Maximum sum = 24

복잡도 분석

시간 복잡도는 O(N × B)입니다. 여기서 N은 배열의 크기, B는 각 숫자의 비트 연산 횟수(최대 32)입니다. 공간 복잡도는 세트 비트 개수별 합계를 저장하는 배열 때문에 O(1), 즉 상수 공간으로 처리할 수 있습니다.