Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 요소를 재배열해 회문을 만들 수 있는 하위 배열 개수 구하기

문제 소개

정수로 이루어진 배열이 주어졌을 때, 해당 배열에서 만들 수 있는 모든 하위 배열(sub-array) 중에서 요소들을 재배열했을 때 유효한 회문(palindrome)을 형성할 수 있는 하위 배열의 개수를 계산하는 것이 이번 문제의 목표입니다. 회문이란 앞에서부터 읽으나 뒤에서부터 읽으나 동일하게 배치된 시퀀스를 의미합니다.

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

출력 − 요소를 재배열하여 회문을 만들 수 있는 하위 배열의 개수: 9

설명 − 회문으로 재배열 가능한 유효한 하위 배열은 {3}, {3}, {1}, {4}, {2}, {1}, {5}, {1, 2, 1}, {1, 3, 1} 입니다. 따라서 총 개수는 9개입니다.

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

출력 − 요소를 재배열하여 회문을 만들 수 있는 하위 배열의 개수: 8

설명 − 회문으로 재배열 가능한 유효한 하위 배열은 {2}, {5}, {5}, {2}, {1}, {5, 2, 5}, {2, 5, 2}, {2, 5, 5, 2} 입니다. 따라서 총 개수는 8개입니다.

핵심 아이디어: 비트마스크와 XOR

어떤 시퀀스가 회문으로 재배열될 수 있으려면, 홀수 번 등장하는 요소가 최대 하나여야 합니다. 이 성질을 활용하면 각 요소 값을 비트 위치에 대응시키고, 하위 배열을 확장할 때마다 XOR 연산으로 등장 횟수의 홀짝성(패리티)을 추적할 수 있습니다.

  • XOR은 같은 값이 두 번 나오면 해당 비트를 다시 0으로 되돌리므로, 짝수 번 등장한 요소는 마스크에서 사라집니다.
  • 최종 비트마스크가 0이라면 모든 요소가 짝수 번 등장한 것이고,
  • 최종 비트마스크가 2의 거듭제곱(비트가 하나만 켜진 경우)이라면 단 하나의 요소만 홀수 번 등장한 것입니다.

두 경우 모두 회문 재배열이 가능하므로 카운트를 증가시키면 됩니다.

알고리즘 접근 방식

  • 정수 배열을 입력받아 배열의 크기를 계산하고, 이후 처리를 위해 함수에 전달합니다.
  • 회문 하위 배열의 개수를 저장할 변수 count를 선언합니다.
  • 0부터 배열 크기까지 FOR 루프를 시작하여 시작 인덱스를 지정합니다.
  • 내부 루프에서는 long long 타입 변수에 1LL << arr[j] 값을 대입하고, temp = temp ^ val로 패리티를 갱신합니다.
  • 불리언 변수 안에서 체크 함수를 호출하여 true 또는 false를 반환받습니다.
  • temp가 0LL이거나 ch가 true라면 count를 1 증가시킵니다.
  • 최종적으로 count를 반환하고 결과를 출력합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
bool check(long long temp){
   return !(temp & (temp - 1LL));
}
int palindromes_rearrange(int arr[], int size){
   int count = 0;
   for (int i = 0; i < size; i++){
      long long temp = 0LL;
      for (int j = i; j < size; j++){
         long long val = 1LL << arr[j];
         temp = temp ^ val;
         bool ch = check(temp);
         if (temp == 0LL || ch){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = { 3, 3, 1, 4, 2, 1, 5};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of sub-arrays whose elements can be re-arranged to form palindromes are:
"<<palindromes_rearrange(arr, size);
   return 0;
}

실행 결과

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

Count of sub-arrays whose elements can be re-arranged to form palindromes are: 9

복잡도 분석

이 알고리즘은 시작 인덱스와 끝 인덱스에 대해 두 겹의 루프를 사용하므로 시간 복잡도는 O(n²)이며, 추가 공간은 상수 수준만 필요하므로 공간 복잡도는 O(1)입니다. 완전 탐색으로 매번 빈도를 다시 세는 O(n³) 방식보다 XOR 비트마스크를 활용하면 각 단계를 O(1)에 처리할 수 있어 훨씬 효율적입니다.