정수 문자열이 주어지고 정수 형식에서 6으로 나눌 수 있는 부분 문자열의 수를 결정해야 하는 문제를 살펴보겠습니다. 입력은 숫자(정수)로 구성된 String 형식이라는 점에 유의해야 합니다. 다만, 정수로 간주하여 나누어 검사를 진행합니다(문자열 입력의 ASCII 값은 사용하지 않음).
입력
str = “648”
출력
설명
하위 문자열 "6", "48" 및 "648"은 6으로 나눌 수 있습니다.
입력
str = “38342”
출력
4
설명
하위 문자열 "3834", "342", "834" 및 "42"는 6으로 나눌 수 있습니다.
무차별 대입 접근
사용자는 가능한 모든 하위 문자열을 확인하여 6으로 나눌 수 있는지 확인할 수 있습니다. 부분 문자열이 나눌 수 있는 경우 추가로 계산합니다. 이 방법은 문제를 해결하는 데 시간이 더 오래 걸리고 작업을 완료하는 데 O(n2) 시간이 걸립니다.
예시
#include <bits/stdc++.h>
using namespace std;
int
str_to_int (string str, int i, int j) {
int temp = 0;
for (; i <= j; i++) {
temp = temp * 10 + (str[i] - '0');
}
return temp;
}
int main () {
char str[] = "24661";
int n = strlen (str);
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int temp = str_to_int (str, i, j);
if (temp % 6 == 0) count++;
}
}
cout << count << endl;
return 0;
} 출력
6
효율적인 접근
숫자의 마지막 자릿수는 2로 나눌 수 있어야 6으로 나눌 수 있습니다. 총 자릿수는 3이어야 합니다. 이전에 계산된 답변을 추적하여 동적 프로그래밍을 활용하여 솔루션을 찾을 수 있습니다.
f(i,s) - Σin-1 f(i,0)을 제공하는 모듈로 3의 자릿수 합이 s인 i번째 인덱스의 문자열 수입니다.
문자열의 i번째 자리를 이라고 합니다. 이제 f(i,s)에서 짝수이고 i + 1로 시작하는 모든 부분 문자열을 찾아야 합니다. (a+s)가 3으로 나누어지면 추가 부분 문자열이 생성될 수 있습니다. 따라서 반복 관계가 형성되었습니다. ,
f(i,s) =f(i + 1, (s + a)%3) + ( a%2 ==0 AND (a+s)%3 ==0).
예시 2
#include <bits/stdc++.h>
using namespace std;
int find(int i, int s, char str[], int dp[][3]){
// when reached end of string.
if (i == strlen(str))
return 0;
// if already computed then return result.
if (dp[i][s] != -1)
return dp[i][s];
int a = str[i] - '0';
int ans = ((a+s)%3 == 0 && a%2 == 0) + find(i+1, (s+a)%3, str, dp);
return dp[i][s] = ans;
}
int main(){
char str[] = "24661";
int n = strlen(str);
// dp array to store all states.
int dp[n+1][3];
memset(dp, -1, sizeof dp);
int count = 0;
for (int i = 0; i < n; i++){
// if any position contains 0 increment count.
if (str[i] == '0')
count++;
// Passing previous sum modulo 3 = 0 to recursive function.
else
count += find(i, 0, str, dp);
}
cout << "Number of substrings divisible by 6: " << count << endl;
return 0;
} 출력
Number of substrings divisible by 6: 6
시간 복잡도:O(N)
결론
이 자습서에서는 동적 프로그래밍을 사용하여 정수 문자열에서 6으로 나눌 수 있는 부분 문자열의 수를 찾는 방법을 배웠습니다. 동일한 프로그램이 C, Java, Python 등과 같은 다른 언어로 작성될 수 있습니다. 이 강의가 도움이 되었기를 바랍니다.