두 개의 문자열 numo와 demo가 입력으로 주어졌을 때, 두 문자열이 공통으로 가지는 약수(공약수)의 개수를 구하는 것이 목표입니다. 여기서 문자열의 '약수(divisor)'는 다음과 같이 정의됩니다. 부분 문자열 sub1이 문자열 str의 약수가 되려면, sub1을 여러 번 반복하여 str 전체를 만들어낼 수 있어야 합니다. 예를 들어 str = "abcabcabc"일 때 sub1 = "abc"는 str의 약수입니다.
예제
입력 1
numo = "abababab" demo = "abababababababab"
출력 1
주어진 문자열의 공약수 개수: 3
설명
두 문자열은 다음과 같은 약수 부분 문자열로 생성할 수 있습니다. "ab", "abab", "abababab"
입력 2
numo = "pqqppqqp" demo = "pqpq"
출력 2
주어진 문자열의 공약수 개수: 0
설명
두 문자열 사이에는 공약수가 존재하지 않습니다. numo의 약수: "pqqp", demo의 약수: "pq"
접근 방법
어떤 부분 문자열 sub1이 문자열 str의 약수가 되려면 다음 두 조건을 반드시 만족해야 합니다.
- sub1은 str의 접두사(prefix)여야 합니다.
- sub1의 길이는 str의 길이를 나누어 떨어지게 해야 합니다.
따라서 이 조건들을 numo와 demo 양쪽에 대해 검사하고, 조건을 만족할 때마다 카운트를 증가시키면 됩니다. 알고리즘의 동작 과정은 다음과 같습니다.
- 문자열 numo와 demo를 입력받습니다.
- verify(string str, int val) 함수는 문자열 str과 정수 val을 받아, 인덱스 0부터 val-1까지의 부분 문자열을 반복하여 str을 생성할 수 있는지 검사하고, 가능하면 1을 반환합니다.
- common_divisor(string numo, string demo) 함수는 두 문자열을 받아 공약수의 개수를 반환합니다.
- 카운트를 0으로 초기화합니다.
- 입력 문자열들의 길이를 계산한 뒤, 더 짧은 길이를 min_val에 저장합니다.
- for 루프를 사용해 i = 1부터 min_val까지 순회합니다.
- 현재 길이 i가 numo_size와 demo_size 모두를 나누어 떨어지게 하고, 동시에 접두사도 일치하는지(numo.substr(0, i) == demo.substr(0, i)) 확인합니다.
- 조건을 만족하면 verify() 함수를 호출하여 길이 i의 부분 문자열이 실제로 numo와 demo 양쪽의 약수인지 검사합니다.
- verify(numo, i)와 verify(demo, i)가 모두 1을 반환하면 카운트를 증가시킵니다.
- for 루프가 종료되면 카운트를 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int verify(string str, int val){
int length = str.length();
for (int i = 0; i < length; i++){
if(str[i] != str[i % val]){
return 0;
}
}
return 1;
}
int common_divisor(string numo, string demo){
int count = 0;
int numo_size = numo.size();
int demo_size = demo.size();
int min_val = min(numo_size, demo_size);
for(int i = 1; i <= min_val; i++){
if(numo_size % i == 0){
if(demo_size % i == 0){
if(numo.substr(0, i) == demo.substr(0, i)){
if(verify(numo, i)==1){
if(verify(demo, i)==1){
count++;
}
}
}
}
}
}
return count;
}
int main(){
string numo = "abababab";
string demo = "abababababababab";
cout<<"Count the number of common divisors of the given strings are: "
<<common_divisor(numo, demo);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Count the number of common divisors of the given strings are: 3