C++에서 첫 문자와 끝 문자가 같은 부분 문자열 개수 구하기

문제 소개

문자열 str이 주어졌을 때, str의 부분 문자열 중 첫 번째 문자와 마지막 문자가 서로 같은 것의 개수를 세는 것이 이번 문제의 목표입니다. 예를 들어 입력이 "baca"라면 조건을 만족하는 부분 문자열은 "b", "a", "c", "a", "aca"로 총 5개입니다.

예시로 이해하기

입력 − str="abaefgf"

출력 − 첫 문자와 끝 문자가 같은 부분 문자열의 개수: 9

설명 − 조건을 만족하는 부분 문자열은 다음과 같습니다.

"a", "b", "a", "e", "f", "g", "f", "aba", "fgf" → 총 9개

입력 − str="abcdef"

출력 − 첫 문자와 끝 문자가 같은 부분 문자열의 개수: 6

설명 − 모든 문자가 서로 다르므로 길이 1짜리 부분 문자열만 조건을 만족합니다.

"a", "b", "c", "d", "e", "f" → 총 6개

방법 1: 완전 탐색(Brute Force)

가장 직관적인 방법은 가능한 모든 부분 문자열을 하나씩 검사하는 것입니다. 모든 길이의 부분 문자열을 check() 함수에 넘기고, 해당 부분 문자열이 같은 문자로 시작하고 끝난다면 카운트를 1 증가시킵니다.

문자열 str을 입력받고, 길이를 str.size()로 구합니다.
check(string str) 함수는 전달받은 부분 문자열의 첫 문자와 마지막 문자가 같은지(str[0] == str[length-1]) 비교하여, 같으면 1을 반환합니다.
check_Start_End(string str, int length) 함수는 str과 그 길이를 입력으로 받아, 조건을 만족하는 부분 문자열의 개수를 반환합니다.
count를 0으로 초기화합니다.
이중 for 루프로 str을 순회합니다. 바깥 루프는 i=0부터 i<length까지, 안쪽 루프는 j=1부터 j<=length-i까지 반복합니다.
substr(i, j)로 시작 위치와 길이를 조합해 모든 부분 문자열을 만들고, 각각을 check()에 전달합니다. 반환값이 1이면 count를 증가시킵니다.
모든 반복이 끝나면 count에는 조건을 만족하는 부분 문자열의 총 개수가 담겨 있습니다.
count를 결과로 반환합니다.

이 방법은 모든 부분 문자열을 생성하고 잘라내야 하므로 시간 복잡도가 O(n³)에 가깝습니다. 문자열이 길어질수록 비효율적이라는 단점이 있습니다.

방법 2: 빈도수를 이용한 효율적 접근

문제를 자세히 살펴보면 정답은 원본 문자열에서 각 문자의 등장 빈도에 의해 결정된다는 사실을 알 수 있습니다.

예를 들어 "bacba"에서 'b'는 2번 등장합니다. 'b'로 시작하고 'b'로 끝나는 부분 문자열은 "b", "bacb", "b"로 3개이며, 이는 2 + C(2, 2) = 3으로 계산됩니다. 일반화하면 어떤 문자의 빈도가 f일 때, 해당 문자로 시작하고 끝나는 부분 문자열의 개수는 f × (f + 1) / 2입니다.

따라서 먼저 각 문자의 빈도를 구한 뒤, 문자마다 (빈도 + 1)C₂ 즉 freq × (freq + 1) / 2를 정답에 더해 주면 됩니다.

문자열 str을 입력받고 길이를 구합니다.
count를 0으로 초기화합니다.
알파벳 빈도를 저장할 크기 26의 배열 arr[26]을 준비합니다.
문자열을 한 번 순회하며 arr[str[i] - 'a']++로 각 문자의 빈도를 기록합니다.
빈도 배열을 순회하며 각 값 arr[i]에 대해 arr[i] × (arr[i] + 1) / 2를 count에 누적합니다.
최종 count를 결과로 반환합니다.

이 방법은 문자열을 두 번만 순회하면 되므로 시간 복잡도가 O(n)으로 매우 효율적입니다.

예제 코드 1: 완전 탐색

#include <bits/stdc++.h>
using namespace std;
int check(string str){
    int length = str.length();
    if(str[0] == str[length-1]){
        return 1;
    }
    return 0;
}
int check_Start_End(string str, int length){
    int count = 0;
    for (int i = 0; i < length; i++){
        for (int j = 1; j <= length-i; j++){
            if (check(str.substr(i, j))){
                count++;
            }
        }
    }
    return count;
}
int main(){
    string str = "bcbdedfef";
    int length = str.length();
    cout<<"Count of substrings with same first and last characters are: "<<check_Start_End(str, length);
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −

Count of substrings with same first and last characters are: 13

예제 코드 2: 효율적 접근

#include <bits/stdc++.h>
using namespace std;
#define maximum 26
int check_Start_End(string str, int length){
    int count = 0;
    int arr[maximum] = {0};
    for(int i=0; i<length; i++){
        arr[str[i] - 'a']++;
    }
    for (int i=0; i<maximum; i++){
        count = count + (arr[i]*(arr[i]+1)/2);
    }
    return count;
}
int main(){
    string str = "bcbdedfef";
    int length = str.length();
    cout<<"Count of substrings with same first and last characters are: "<<check_Start_End(str, length);
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −

Count of substrings with same first and last characters are: 13

마무리

같은 문자로 시작하고 끝나는 부분 문자열의 개수는 완전 탐색으로도 구할 수 있지만, 각 문자의 빈도수를 활용하면 O(n) 시간에 훨씬 빠르게 계산할 수 있습니다. 문자열 길이가 큰 문제에서는 빈도수 기반 접근이 확실히 유리합니다.