이 문제의 목표는 동일한 문자로만 구성된 길이 K인 부분 문자열(substring)이 문자열 안에 몇 번 나타나는지 그 최대 개수를 구하는 것입니다. 하나의 문자열 s와 정수 K가 주어졌을 때, 길이가 K이면서 모든 문자가 같은 부분 문자열의 등장 횟수를 세고, 그중 가장 많이 나타난 횟수를 출력해야 합니다.
예제를 통해 문제를 자세히 살펴보겠습니다.
입력 예시 1
s = "tuuxyyuuc", K = 2
출력 예시 1
2
설명
길이가 2이면서 동일한 문자로 구성된 부분 문자열은 "uu"와 "yy"입니다. 이때 "yy"는 1번만 등장하지만, "uu"는 2번 등장합니다. 따라서 최댓값인 2가 출력됩니다.
입력 예시 2
s = "hhigggff", K = 3
출력 예시 2
1
접근 방법
- Max() 함수에서 최종 답을 저장할 int형 변수 ans = 0, 문자열의 길이를 저장할 size = str.size()를 초기화하고, 검사할 문자를 저장할 char형 변수 c를 선언합니다.
- j = 0부터 j < 26까지 반복하면서 c = 'a' + j로 설정하여 알파벳 소문자 각각에 대해 검사를 진행합니다.
- 현재 문자로 이루어진 부분 문자열의 등장 횟수를 저장할 변수 CurrCh = 0을 초기화합니다.
- i = 0부터 i <= size - K까지 반복하며, 만약 (str[i] != c)라면 continue; 문으로 건너뜁니다.
- 현재 문자로 이루어진 연속 구간의 길이를 저장할 count = 0을 초기화합니다.
- 조건식 (i < size && count != K && str[i] == c)을 가진 while 루프를 생성하고, 루프 내부에서 i와 count를 증가시킵니다. while 루프가 끝나면 i를 1 감소시킵니다.
- (count == K)인지 확인하고, 참이라면 CurrCh를 증가시킵니다.
- 두 번째 for 루프를 종료한 뒤, ans = max(ans, CurrCh)로 ans 값을 갱신합니다.
- 마지막으로 첫 번째 for 루프를 종료하고 ans를 반환합니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
int Max(string str, int K){
int ans = 0, size = str.size();
char c;
//모든 알파벳 문자에 대해 검사
for (int j = 0; j < 26; j++){
c = 'a' + j;
//현재 문자에 대한 검사
int CurrCh = 0;
for (int i = 0; i <= size - K; i++){
if (str[i] != c)
continue;
//부분 문자열의 길이 계산
int count = 0;
while (i < size && count != K && str[i] == c){
i++;
count++;
}
i--;
//부분 문자열의 길이가 K이면 CurrCh 증가
if (count == K)
CurrCh++;
}
//ans 값 갱신
ans = max(ans, CurrCh);
}
return ans;
}
//메인 함수
int main(){
string str = "tuuuxyuuu";
int K = 3;
cout << Max(str, K);
return 0;
}실행 결과
2
위 코드는 문자열 "tuuuxyuuu"에서 길이가 3이고 동일한 문자로 구성된 부분 문자열을 찾습니다. 'u'가 3번 연속으로 나타나는 구간이 총 2번 존재하므로 결과값으로 2가 출력됩니다.