이 문제에서는 숫자로 해석될 수 있는 문자열이 제공됩니다. 이제 문자열을 두 부분으로 분할하여 첫 번째 부분을 A로 나누고 두 번째 부분을 B로 나눌 수 있도록 해야 합니다(두 개의 정수가 주어짐). 예를 들어 -
Input : str = "123", a = 12, b = 3 Output : YES 12 3 "12" is divisible by a and "3" is divisible by b. Input : str = "1200", a = 4, b = 3 Output : YES 12 00 Input : str = "125", a = 12, b = 3 Output : NO
이제 이 문제에서 우리는 프로그램을 더 빠르게 만들 수 있는 사전 계산을 수행한 다음 더 높은 제약 조건에서 작동할 수 있습니다.
해결책을 찾기 위한 접근 방식
이 접근 방식에서는 문자열을 통해 두 개의 루프를 실행할 것입니다. 첫 번째는 처음부터 끝까지, 두 번째는 끝에서 시작까지입니다. 이제 모든 지점에서 첫 번째 루프에서 b로 구성된 정수의 모드를 취하면 답을 찾을 수 있습니다.
예시
#include <bits/stdc++.h>
using namespace std;
void divisionOfString(string &str, int a, int b){
int n = str.length();
vector<int> mod_a(n+1, 0); //
mod_a[0] = (str[0] - '0')%a;
for (int i=1; i<n; i++) // front loop for calculating the mod of integer with a
mod_a[i] = ((mod_a[i-1]*10)%a + (str[i]-'0'))%a;
vector<int> mod_b(n+1, 0);
mod_b[n-1] = (str[n-1] - '0')%b;
int power10 = 10; // as we have assigned answer to last index
for (int i= n-2; i>=0; i--){ // end loop for calculating the mod of integer with b
mod_b[i] = (mod_b[i+1] + (str[i]-'0')*power10)%b;
power10 = (power10 * 10) % b;
}
for (int i=0; i<n-1; i++){ // finding the division point
if (mod_a[i] != 0) // we can skip through all the positions where mod_a is not zero
continue;
if (mod_b[i+1] == 0){ // now if the next index of mod_b is also zero so that is our division point
cout << "YES\n";
/*******Printing the partitions formed**********/
for (int k=0; k<=i; k++)
cout << str[k];
cout << " ";
for (int k=i+1; k < n; k++)
cout << str[k];
return;
}
}
cout << "NO\n"; // else we print NO
}
// Driver code
int main(){
string str = "123"; // given string
int a = 12, b = 3;
divisionOfString(str, a, b);
return 0;
} 출력
YES 12 3
위 코드 설명
이 접근 방식에서 우리는 현재 모든 분할에서 형성된 숫자의 나머지를 계산했습니다. 첫 번째 숫자는 로 나눌 수 있어야 하므로 순방향 루프를 실행하고 해당 숫자의 모드를 로 저장합니다. b를 사용하여 역방향 루프를 실행하고 mod를 저장합니다. 임의의 위치에서 a의 mod가 0이고 다음 인덱스가 있는 b가 있는 mod가 0이면 그것이 우리의 답이 될 것이며 따라서 인쇄합니다.
결론
이 자습서에서는 파티션 번호를 두 개의 나눌 수 있는 부분으로 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식(Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.