C++로 문자열의 모든 부분 문자열에 등장하는 모음 개수 구하기

영어 알파벳으로 이루어진 문자열 str이 주어졌을 때, str의 모든 부분 문자열에 등장하는 모음의 총 개수를 구하는 것이 목표입니다. 예를 들어 문자열이 "abcde"라면 부분 문자열은 "a", "b", "c", "d", "e", "ab", "bc", "cd", "de", "abc", "bcd", "cde", "abcd", "bcde", "abcde"가 되며, 이들 안에 포함된 모음의 개수는 총 10개입니다('a'와 'e'가 여러 번 등장).

예시

입력

str = "aloe"

출력

주어진 문자열의 모든 부분 문자열에 등장하는 모음의 개수:
14

설명

부분 문자열은 다음과 같습니다.
"a", "l", "o", "e", "al", "lo", "oe", "alo", "loe", "aloe"
이들에 포함된 모음의 총 개수는 14개입니다.

입력

str = "http"

출력

주어진 문자열의 모든 부분 문자열에 등장하는 모음의 개수:
0

설명

부분 문자열은 다음과 같습니다.
"h", "t", "t", "p", "ht", "tt", "tp", "htt", "ttp", "http"
이들에 포함된 모음의 총 개수는 0개입니다.

풀이 접근 방식

이 접근 방식에서는 vec라는 벡터를 생성하고, vec[i]에 i번째 문자가 모든 부분 문자열에서 등장하는 횟수를 저장합니다.

0번째 문자는 n개의 부분 문자열에 등장합니다(여기서 n은 문자열 str의 길이입니다).

i번째 문자는 다음 세 값의 조합만큼 등장합니다. 해당 문자를 포함하는 부분 문자열의 수(n−i)에, i번째 문자와 바로 앞 문자를 함께 포함하는 부분 문자열의 수(vec[i−1])를 더한 뒤, 앞 문자들만으로 구성된 부분 문자열의 수(i)를 빼면 됩니다.

알고리즘 단계

문자열 str을 입력받습니다.
substring_vowels_count(string str, int length) 함수는 str과 길이를 받아 주어진 문자열의 모든 부분 문자열에 등장하는 모음의 개수를 반환합니다.
count를 0으로 초기화합니다.
정수형 벡터 vec를 선언합니다.
for 반복문으로 i=0부터 i<length까지 순회하면서, str의 모든 부분 문자열에서 i번째 위치의 문자가 등장하는 횟수로 vec를 채웁니다.
i=0인 경우, 0번째 문자의 등장 횟수는 length입니다. push_back(length)로 vec[0]=length를 설정합니다.
나머지 문자들은 push_back(temp_1 + temp_2)로 설정하며, 여기서 temp_1=length−i, temp_2=vec[i−1]−i입니다.
다시 for 반복문으로 str을 순회하면서 str[i]가 모음(a, e, i, o, u)이면 count에 vec[i]를 더합니다.
모든 순회가 끝나면 count에 부분 문자열 내 모음의 총 등장 횟수가 저장됩니다.
결과로 count를 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int substring_vowels_count(string str, int length){
    int count = 0;
    vector<int> vec;
    for (int i = 0; i < length; i++){
       if (i == 0){
          vec.push_back(length);
       } else {
          int temp_1 = length − i;
          int temp_2 = vec[i − 1] − i;
          vec.push_back(temp_1 + temp_2);
       }
    }
    for (int i = 0; i < length; i++){
       if(str[i] == 'a' || str[i] == 'i' || str[i] == 'e' || str[i] == 'o' || str[i] == 'u'){
          count = count + vec[i];
       }
    }
    return count;
}
int main(){
    string str = "honesty";
    int length = str.length();
    cout<<"주어진 문자열의 모든 부분 문자열에 등장하는 모음의 개수: "<<substring_vowels_count(str, length);
    return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

주어진 문자열의 모든 부분 문자열에 등장하는 모음의 개수: 28