1과 0으로만 구성된 두 개의 이진 문자열 str_1과 str_2가 주어집니다. 해야 할 작업은 먼저 str_2에서 만들 수 있는 서로 다른 순환 순열들의 집합(SET)을 구성한 뒤, 집합의 각 원소를 문자열 str_1과 XOR 연산하고 그 결과가 0이 되는지 확인하는 것입니다. 결과가 0이라면 해당 경우를 카운트하고, 그렇지 않다면 무시합니다.
예제로 이해해 보기
입력 - string str_1 = "1111", string str_2 = "1111"
출력 - 다른 이진 문자열과 XOR 결과가 0이 되는 순환 순열의 개수: 4
설명 - str_2로 만들 수 있는 순환 순열의 집합은 {1111}입니다. 여기에 str_1을 XOR 연산하면 {1111} ^ "1111" = 0이 됩니다. str_2의 네 자리가 모두 같은 문자이므로 4개의 순열이 존재할 수 있고, 따라서 출력은 4가 됩니다.
입력 - string str_1 = "1101", string str_2 = "1101"
출력 - 다른 이진 문자열과 XOR 결과가 0이 되는 순환 순열의 개수: 1
설명 - str_2로 만들 수 있는 순환 순열의 집합은 {1101, 1110, 1011, 0111}입니다. 각 원소를 str_1과 XOR 연산하면 다음과 같습니다.
{1101} ^ 1101 = 0
{1110} ^ 1101 ≠ 0
{1011} ^ 1101 ≠ 0
{0111} ^ 1101 ≠ 0
결과가 0이 되는 경우는 단 하나뿐이므로 개수는 1입니다.
프로그램에서 사용된 접근 방식
- 두 이진 문자열 str_1과 str_2를 입력받아 이후 처리를 위해 cyclic_permutation() 함수로 전달합니다.
- str_2를 str_2 + str_2로 확장한 뒤 마지막 한 글자를 제거(str_2.substr(0, str_2.size() - 1))하여, str_2의 모든 순환 순열을 하나의 문자열 안에 포함시킵니다.
- str_1, 구분자 '$', 확장된 str_2를 이어 붙여 새로운 문자열 str을 만들고 그 길이를 계산한 후, 문자열 길이와 같은 크기의 정수 배열을 선언합니다.
- 문자열 str과 배열을 인자로 전달하여 check() 함수(Z 알고리즘 기반)를 호출합니다.
- check() 함수 내부에서는 다음을 수행합니다.
- start와 end 두 변수를 선언하고 0으로 초기화합니다.
- 문자열의 길이를 계산합니다.
- i가 1부터 문자열 길이 - 1까지 반복하는 FOR 루프를 시작합니다. i가 end보다 크면 start와 end를 i로 설정한 뒤, end가 문자열 길이보다 작고 str[end - start]가 str[end]와 같은 동안 end를 1씩 증가시키는 WHILE 루프를 실행합니다.
- arr[i]를 end - start로 설정한 후 end를 1 감소시킵니다.
- 그렇지 않은 경우(i ≤ end)에는 임시 변수 temp를 i - start로 설정합니다. arr[temp]가 end - i + 1보다 작으면 arr[i]를 arr[temp]로 설정하고, 그렇지 않으면 start를 i로 설정한 뒤 앞서와 동일한 WHILE 루프를 수행하여 arr[i]를 end - start로 설정하고 end를 1 감소시킵니다.
- i가 1부터 문자열 str의 길이 - 1까지 반복하면서 arr[i]가 str_1의 길이와 같으면 count를 1 증가시킵니다.
- count를 반환하고 결과를 출력합니다.
이 접근 방식은 Z 알고리즘을 활용하므로, 모든 순환 순열을 하나씩 직접 생성해 비교하는 O(n²) 방식보다 훨씬 효율적인 O(n) 시간 복잡도로 문제를 해결할 수 있다는 장점이 있습니다.
예제
#include <bits/stdc++.h>
using namespace std;
void check(string str, int arr[]) {
int start = 0, end = 0;
int len = str.length();
for (int i = 1; i <= len - 1; i++) {
if (i > end) {
start = i;
end = i;
while (end < len && str[end - start] == str[end]) {
end++;
}
arr[i] = end - start;
end--;
} else {
int temp = i - start;
if (arr[temp] < end - i + 1) {
arr[i] = arr[temp];
} else {
start = i;
while (end < len && str[end - start] == str[end]) {
end++;
}
arr[i] = end - start;
end--;
}
}
}
}
int cyclic_permutation(string str_1, string str_2) {
int count = 0;
str_2 = str_2 + str_2;
str_2 = str_2.substr(0, str_2.size() - 1);
string str = str_1 + "$" + str_2;
int len = str.length();
int arr[len];
check(str, arr);
for (int i = 1; i <= len - 1; i++) {
if (arr[i] == str_1.length()) {
count++;
}
}
return count;
}
int main() {
string str_1 = "1111";
string str_2 = "1111";
cout << "Count of cyclic permutations having XOR with other binary string as 0 are: " << cyclic_permutation(str_1, str_2);
return 0;
}
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
출력
Count of cyclic permutations having XOR with other binary string as 0 are: 4