C++에서 비트 교환으로 XOR이 0이 되는 부분 배열 개수 최대화하기

문제 이해하기

정수 값들로 이루어진 배열 Arr[]가 주어졌을 때, XOR 값이 0이 되는 부분 배열(subarray)의 최대 개수를 구하는 것이 목표입니다. 단, 임의의 부분 배열 안에서는 비트를 몇 번이든 자유롭게 교환(swap)할 수 있습니다.

참고: 1 ≤ Arr[i] ≤ 10¹⁸

비트 교환을 통해 어떤 부분 배열의 XOR을 0으로 만들려면 다음 두 가지 조건을 반드시 충족해야 합니다.

• 범위(왼쪽~오른쪽) 내에서 설정된 비트(set bit)의 총 개수가 짝수일 것

• 주어진 범위에서 비트 개수의 합이 최댓값(범위 내 가장 큰 설정 비트 수)의 2배 이하일 것, 즉 합 ≤ 2 × 최댓값

다양한 입출력 시나리오를 살펴보겠습니다.

입력 − Arr[] = { 1, 2, 5, 4 }

출력 −

첫 번째 조건만 만족하는 부분 배열 : 4개

두 조건을 모두 만족하는 부분 배열 : 3개

입력 − Arr[] = { 3, 7, 2, 9 }

출력 −

첫 번째 조건만 만족하는 부분 배열 : 6개

두 조건을 모두 만족하는 부분 배열 : 3개

풀이 접근 방법

이 접근법의 핵심은 앞서 언급한 두 조건을 활용하는 것입니다. 비트 교환으로 부분 배열의 XOR을 0으로 만들려면, 범위 내 설정 비트의 개수가 짝수이면서 동시에 비트 개수의 합이 최댓값의 2배 이하(합 ≤ 2 × 최댓값)여야 한다는 점에 착안합니다.

• 입력 배열 Arr[]를 받아 길이를 계산합니다.

• 함수 removeSubarr(int arr[], int len)은 조건 2를 만족하지 않는 부분 배열의 개수를 반환합니다.

• 초기 카운트를 0으로 설정합니다.

• for 루프로 배열을 순회하며 sum과 maxVal 변수를 사용합니다.

• 또 다른 for 루프로 최대 60개 길이의 부분 배열 범위를 탐색합니다. 60을 초과하면 조건 2는 절대 거짓이 될 수 없기 때문입니다.

• 각 요소를 sum에 더하고, maxVal에는 최댓값을 저장합니다.

• sum이 짝수이면서 2 × maxVal > sum이라면 조건 2를 충족하지 않으므로 카운트를 증가시킵니다.

• 모든 루프가 종료되면 count를 반환합니다.

• 함수 findSubarrays(int arr1[], int len1)는 입력 배열과 그 길이를 받아 위 두 조건을 모두 만족하는 부분 배열의 개수를 반환합니다.

• 조건 1만 만족하는 부분 배열의 개수를 계산하기 위해 접두사(prefix) 배열을 사용합니다.

• for 루프로 배열을 순회하면서 각 요소를 __builtin_popcountll(arr1[i]), 즉 해당 값의 설정 비트 개수로 변환합니다.

• for 루프로 접두사 배열을 채웁니다. 첫 번째 요소를 제외하고 prefix[i] = prefix[i] + prefix[i - 1]로 설정합니다.

• 접두사 배열에서 홀수 값과 짝수 값의 개수를 각각 셉니다.

• tmp1 = (oddcount × (oddcount − 1)) / 2, tmp2 = (evencount × (evencount − 1)) / 2로 계산하고, 결과(result)는 두 값의 합입니다.

• 이 결과가 곧 조건 1만 만족하는 부분 배열의 총 개수가 됩니다.

• 결과를 출력합니다.

• result = result − removeSubarr(arr1, len1)로 결과를 갱신합니다.

• 이제 결과에는 두 조건을 모두 만족하는 부분 배열의 개수가 담깁니다.

• 갱신된 결과를 다시 출력합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
// 조건 2를 만족하지 않는 부분 배열의 개수를 세는 함수
int removeSubarr(int arr[], int len){
    int count = 0;
    for (int i = 0; i < len; i++){
        int sum = 0;
        int maxVal = 0;

        for (int j = i; j < min(len, i + 60); j++){
            sum = sum + arr[j];
            maxVal = arr[j] > maxVal ? arr[j]: maxVal;

            if (sum % 2 == 0){
                if( 2 * maxVal > sum)
                    { count++; }
            }
        }
    }
    return count;
}
int findSubarrays(int arr1[], int len1){
    int prefix[len1];
    int oddcount, evencount;
    int result;
    for (int i = 0; i < len1; i++)
    { arr1[i] = __builtin_popcountll(arr1[i]); }

    for (int i = 0; i < len1; i++){
        prefix[i] = arr1[i];
        if (i != 0)
            { prefix[i] = prefix[i] + prefix[i - 1]; }
        }
        oddcount = evencount = 0;
        for (int i = 0; i < len1; i++){
            if (prefix[i] % 2 == 0)
                { evencount = evencount +1; }
            else
                { oddcount = oddcount +1; }

        }
        evencount++;
      int tmp1= ( oddcount * (oddcount-1) )/2;
      int tmp2= ( evencount * (evencount-1) )/2;
      result = tmp1+tmp2;
      cout << "Subarrays satisfying only 1st condition : "<<result << endl;
      cout << "Subarrays satisfying both condition : ";
      result = result - removeSubarr(arr1, len1);
      return result;
   }
   int main()
   { int Arr[] = { 1,2,5,4 };
   int length = sizeof(Arr) / sizeof(Arr[0]);
   cout << findSubarrays(Arr, length);
   return 0;
}

실행 결과

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

Subarrays satisfying only 1st condition : 4
Subarrays satisfying both condition : 3