소문자 알파벳으로만 이루어진 문자열 str과 정수 k가 주어졌을 때, str에서 만들 수 있는 모든 부분 문자열 중 정확히 k개의 서로 다른 문자를 포함하는 경우의 개수를 구하는 것이 목표입니다.
예시
입력
str = "pqr", k = 2
출력
정확히 k개의 서로 다른 문자를 가진 부분 문자열의 개수: 2
설명
정확히 2개의 서로 다른 문자를 가진 부분 문자열은 "pq", "qr"입니다.
입력
str = "stristr", k = 4
출력
정확히 k개의 서로 다른 문자를 가진 부분 문자열의 개수: 10
설명
정확히 4개의 서로 다른 문자를 가진 부분 문자열은 다음과 같습니다.
"stri", "tris", "rist", "istr", "stris", "trist", "ristr", "strist", "tristr", "stristr"
알고리즘 접근 방법
이 접근 방식에서는 크기가 26인 배열 array[26]을 사용하여 문자열 str에 포함된 각 영어 알파벳의 출현 빈도를 저장합니다. 이후 두 개의 for 루프를 이용해 str을 순회하면서, 부분 문자열 내에서 어떤 문자가 처음 등장할 때마다 고유 문자 개수(temp)를 1씩 증가시킵니다. 하나의 부분 문자열에 대한 순회가 끝났을 때 temp 값이 k와 같다면 주어진 조건을 만족하는 부분 문자열이므로 count를 증가시킵니다.
문자열 str을 입력받습니다.
양의 정수 k를 입력받습니다.
함수 substring_k(string str, int length, int k)는 str과 k를 인자로 받아 정확히 k개의 서로 다른 문자를 가진 부분 문자열의 개수를 반환합니다.
count의 초기값을 0으로 설정합니다.
빈도를 저장할 배열 array[26]을 선언합니다.
i = 0부터 i < length까지, j = i부터 j < length까지 두 개의 for 루프로 str을 순회합니다.
temp는 부분 문자열 str[i..j]에 존재하는 고유 문자의 개수를 나타냅니다.
array[str[j] - 'a'] == 0이라면 문자 str[j]가 해당 부분 문자열에서 처음 등장한 것이므로 temp를 증가시킵니다.
그다음 array[str[j] - 'a']++로 현재 문자의 빈도를 증가시킵니다.
temp가 k와 같으면 count를 증가시킵니다.
temp가 k보다 커지면 더 이상 계산할 필요가 없으므로 루프를 종료(break)합니다.
모든 루프가 종료되면 count를 결과로 반환합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
int substring_k(string str, int length, int k){
int count = 0;
int array[26];
for (int i = 0; i < length; i++){
int temp = 0;
memset(array, 0, sizeof(array));
for (int j = i; j < length; j++){
if(array[str[j] - 'a'] == 0){
temp++;
}
array[str[j] - 'a']++;
if (temp == k){
count++;
}
if(temp > k){
break;
}
}
}
return count;
}
int main(){
string str = "abc";
int length = str.length();
int k = 1;
cout<<"정확히 k개의 서로 다른 문자를 가진 부분 문자열의 개수: "<<substring_k(str, length, k);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
정확히 k개의 서로 다른 문자를 가진 부분 문자열의 개수: 3