C++에서 같은 수의 세트 비트를 가진 연속 배열 요소의 최대 개수 구하기

문제 개요

정렬되지 않은 정수 배열이 주어졌을 때, 다음 두 조건을 모두 만족하는 요소들의 최대 개수를 구하는 것이 목표입니다.

각 요소의 세트 비트(set bit) 개수가 서로 동일해야 합니다.
조건을 만족하는 요소들은 배열 안에서 반드시 연속적(contiguous)으로 배치되어 있어야 합니다.

여기서 세트 비트란 이진수 표현에서 값이 1인 비트를 의미합니다.

입출력 예시

예시 1

입력 − int arr[] = { 5, 8, 1, 2, 9, 12 }

출력 − 같은 수의 세트 비트를 가진 연속 배열 요소의 최대 개수: 3

설명 − 배열의 각 요소를 이진수로 변환한 뒤 세트 비트의 개수를 계산하면 다음과 같습니다.

arr[0] = 5  => 0101 => 세트 비트 개수: 2
arr[1] = 8  => 1000 => 세트 비트 개수: 1
arr[2] = 1  => 0001 => 세트 비트 개수: 1
arr[3] = 2  => 0010 => 세트 비트 개수: 1
arr[4] = 9  => 1001 => 세트 비트 개수: 2
arr[5] = 12 => 1100 => 세트 비트 개수: 2

세트 비트 개수가 같으면서 배열에서 연속된 위치에 있는 요소들은 5, 9, 12(모두 세트 비트 2개)입니다. 따라서 조건을 만족하는 연속 요소의 최대 개수는 3입니다.

예시 2

입력 − int arr[] = { 5, 8, 1, 2 }

출력 − 같은 수의 세트 비트를 가진 연속 배열 요소의 최대 개수: 2

설명 − 마찬가지로 각 요소의 세트 비트 개수를 계산합니다.

arr[0] = 5 => 0101 => 세트 비트 개수: 2
arr[1] = 8 => 1000 => 세트 비트 개수: 1
arr[2] = 1 => 0001 => 세트 비트 개수: 1
arr[3] = 2 => 0010 => 세트 비트 개수: 1

세트 비트 개수가 같고 연속적인 요소는 1과 2(세트 비트 1개)뿐입니다. 따라서 최대 개수는 2입니다.

알고리즘 접근 방식

정수형 배열 요소를 입력받습니다.
sizeof 연산자 등을 활용해 배열의 크기를 계산한 뒤 함수에 전달합니다.
현재 연속 길이를 저장할 임시 변수 temp와 최종 결과를 저장할 maximum 변수를 각각 1로 초기화합니다.
vector<int> 타입의 벡터를 생성합니다.
0부터 배열 크기까지 반복하면서 __builtin_popcount() 함수로 각 요소의 세트 비트 개수를 구해 벡터에 저장합니다.
1부터 벡터 크기까지 반복하면서 인접한 두 값(vec[i]와 vec[i-1])을 비교합니다.
두 값이 같으면 temp를 1 증가시키고, 다르면 temp를 1로 초기화합니다.
max() 함수로 temp와 maximum 중 더 큰 값을 maximum에 갱신합니다.
반복이 끝나면 maximum을 반환하고 결과를 출력합니다.

참고: __builtin_popcount(n)는 GCC에서 제공하는 내장 함수로, 정수 n의 이진 표현에서 1의 개수(세트 비트 수)를 매우 빠르게 반환합니다.

C++ 구현 예제

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

// 동일한 세트 비트 개수를 가진 연속 요소의 최대 길이를 계산하는 함수
int maximum_SameBits(int arr[], int size){
    int temp = 1;
    int maximum = 1;
    vector<int> vec;

    // 각 요소의 세트 비트 개수를 벡터에 저장
    for (int i = 0; i < size; i++){
        vec.push_back(__builtin_popcount(arr[i]));
    }

    // 인접한 요소의 세트 비트 개수를 비교
    for (int i = 1; i < vec.size(); i++){
        if (vec[i] == vec[i - 1]){
            temp++;
        }
        else{
            temp = 1;
        }
        maximum = max(maximum, temp);
    }
    return maximum;
}

int main(){
    int arr[] = { 5, 8, 1, 2, 9, 12 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "같은 수의 세트 비트를 가진 연속 배열 요소의 최대 개수: "
         << maximum_SameBits(arr, size);
    return 0;
}

실행 결과

같은 수의 세트 비트를 가진 연속 배열 요소의 최대 개수: 3

복잡도 분석

시간 복잡도: O(n) — 배열을 두 번 선형으로 순회합니다.
공간 복잡도: O(n) — 각 요소의 세트 비트 개수를 저장할 벡터가 추가로 필요합니다.