문제 개요
문자열 str이 주어졌을 때, str의 모든 부분 문자열 중에서 각 문자가 최대 k번까지만 등장하는 부분 문자열의 개수를 구하는 것이 목표입니다. 예를 들어 입력이 "abc"이고 k=1이라면, 조건을 만족하는 부분 문자열은 "a", "b", "c", "ab", "bc", "abc"로 총 6개입니다.
예제로 이해하기
입력 − str = "abc", k = 1
출력 − 각 문자가 최대 1번씩 등장하는 부분 문자열의 개수: 6
설명 − 조건을 만족하는 부분 문자열은 다음과 같습니다.
"a", "b", "c", "ab", "bc", "abc". 총 6개
입력 − str = "bbddehj", k = 1
출력 − 각 문자가 최대 1번씩 등장하는 부분 문자열의 개수: 14
설명 − "bb"처럼 같은 문자가 2번 이상 포함된 부분 문자열은 제외됩니다. 조건을 만족하는 부분 문자열은 다음과 같습니다.
"b", "b", "d", "d", "e", "h", "j", "bd", "de", "eh", "hj", "deh", "ehj", "dehj". 총 14개
접근 방법
이 문제는 여러 가지 방식으로 해결할 수 있습니다. 가장 직관적인 완전 탐색(브루트 포스) 방법은 가능한 모든 부분 문자열을 생성한 뒤, 각 부분 문자열마다 문자별 등장 횟수를 일일이 검사하는 것입니다. 부분 문자열의 개수 자체가 O(n²)개이고 각각을 검사하는 데 O(n)이 소요되므로 전체 시간 복잡도는 O(n³)이 되어 비효율적입니다.
아래 프로그램에서는 이를 개선한 방법을 사용합니다. 시작 위치를 고정한 상태에서 끝 위치를 한 칸씩 늘려가며 문자 빈도 배열을 갱신하고, 특정 문자의 빈도가 k를 초과하는 순간 그 이상은 확장할 수 없으므로 즉시 반복을 중단합니다. 이렇게 하면 각 시작점마다 한 번의 순회만으로 유효한 부분 문자열을 모두 셀 수 있어 전체 시간 복잡도가 O(n²)로 줄어듭니다.
문자열 str과 정수 k를 입력받고, 길이를 str.size()로 계산합니다.
크기 26의 정수 배열 arr을 선언하여 각 알파벳 소문자의 등장 횟수를 저장합니다.
바깥 루프에서 시작 인덱스 i를 0부터 length-1까지 순회하며, 매 반복마다 memset으로 arr을 0으로 초기화합니다.
안쪽 루프에서 끝 인덱스 j를 i부터 length-1까지 늘려가며 arr[str[j] - 'a'] 값을 1씩 증가시킵니다.
새로 추가된 문자의 빈도가 k 이하이면 count를 1 증가시키고, k를 초과하면 break로 안쪽 루프를 종료합니다.
모든 루프가 종료되면 count에는 조건을 만족하는 부분 문자열의 총 개수가 저장되어 있으며, 이를 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int count_k(string str, int len, int k){
int count = 0;
int arr[26];
for (int i = 0; i < len; i++){
memset(arr, 0, sizeof(arr));
for (int j = i; j < len; j++){
arr[str[j] - 'a']++;
if (arr[str[j] - 'a'] <= k)
{ count++; }
else
{ break; }
}
}
return count;
}
int main(){
string str = "bbddehj";
int k = 1;
int length = str.length();
cout<<"Count of substrings with each character occurring at most k times are: "<<count_k(str,
length, k);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Count of substrings with each character occurring at most k times are: 14
복잡도 분석 및 추가 최적화
위 알고리즘의 시간 복잡도는 O(n²)이며, 크기 26의 고정 배열만 사용하므로 공간 복잡도는 O(1)입니다. 여기서 한 단계 더 나아가 투 포인터(슬라이딩 윈도우) 기법을 활용하면 왼쪽 경계와 오른쪽 경계를 각각 한 번씩만 이동시켜 O(n) 시간에 문제를 해결할 수도 있습니다. 문자열의 길이가 매우 긴 경우에는 슬라이딩 윈도우 방식을 적용하는 것이 좋습니다.