문자열 str[]과 정수 n이 주어졌을 때, 우리의 목표는 str[]에서 길이가 n인 모든 부분 문자열을 찾아 그 개수를 구하는 것입니다. 예를 들어 문자열이 "abcde"이고 n=3이라면, 길이가 3인 부분 문자열은 "abc", "bcd", "cde"로 총 3개가 됩니다.
예시로 이해하기
입력 − str[] = "computer", n = 4
출력 − 주어진 문자열에서 만들 수 있는 길이 n의 부분 문자열 개수: 5
설명 − 길이가 4인 부분 문자열은 "comp", "ompu", "mput", "pute", "uter" 입니다.
입력 − str[] = "development", n = 5
출력 − 주어진 문자열에서 만들 수 있는 길이 n의 부분 문자열 개수: 7
설명 − 길이가 5인 부분 문자열은 "devel", "evelo", "velop", "elopm", "lopme", "opmen", "pment" 입니다.
풀이 접근 방식
이 문제는 간단한 수학적 규칙 하나로 해결할 수 있습니다. 문자열 str[]의 전체 길이를 L이라고 하면, 길이가 n인 부분 문자열의 개수는 L − n + 1입니다.
예를 들어 문자열이 "abcdefghi"(길이 9)이고 n = 4라면, 부분 문자열은 "abcd", "bcde", "cdef", "defg", "efgh", "fghi"로 총 6개입니다. 실제로 9 − 4 + 1 = 6으로 공식과 일치하는 것을 확인할 수 있습니다.
알고리즘은 다음과 같습니다.
- 문자열 str을 입력받습니다.
- n을 정수로 입력받습니다.
- 함수 possible_substring(string str, int length, int n)은 문자열과 그 길이, n을 받아 길이가 n인 부분 문자열의 개수를 반환합니다.
- 변수 count를 선언합니다.
- count = length − n + 1 로 설정합니다.
- 최종적으로 count를 결과로 반환합니다.
참고: n이 문자열의 길이보다 크면 만들 수 있는 부분 문자열이 없으므로, 실제 구현 시에는 n > length인 경우 0을 반환하도록 처리해 주는 것이 안전합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int possible_substring(string str, int length, int n){
int count = length - n + 1;
return count;
}
int main(){
string str = "learning";
int length = str.length();
int n = 2;
cout<<"주어진 문자열에서 만들 수 있는 길이 n의 부분 문자열 개수: "<<possible_substring(str, length, n);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
주어진 문자열에서 만들 수 있는 길이 n의 부분 문자열 개수: 7
문자열 "learning"의 길이는 8이고 n = 2이므로, 8 − 2 + 1 = 7개의 부분 문자열이 만들어지는 것을 확인할 수 있습니다.