C++로 세는 부분 문자열 아나그램의 총 개수

문자열 str[]이 입력으로 주어졌을 때, 이 문자열 안에 존재하는 아나그램(anagram) 부분 문자열의 총 개수를 구하는 것이 목표입니다. 두 문자열이 서로 아나그램 관계라는 것은, 두 문자열이 동일한 개수의 문자를 포함하며 모든 문자가 양쪽에 등장하는 경우를 말합니다. 단, 문자의 순서는 달라도 됩니다.

예를 들어 "abc"는 "cba", "bca" 등과 서로 아나그램 관계입니다.

예제로 이해하기

입력 − str[] = "abccb"

출력 − 부분 문자열 아나그램의 총 개수: 4

설명 − 아나그램 쌍은 다음과 같습니다: (b,b), (c,c), (bc,cb), (bcc,ccb)

입력 − str = "aaa"

출력 − 부분 문자열 아나그램의 총 개수: 4

설명 − 아나그램 쌍은 다음과 같습니다: (a,a), (a,a), (a,a), (aa,aa)

풀이 접근 방식

이 문제는 맵(map)을 활용해 해결할 수 있습니다. 맵의 키는 부분 문자열 내 알파벳 빈도를 담은 벡터이고, 값은 그와 같은 빈도 분포를 가진 부분 문자열의 개수입니다.

즉, map<vector<int>, int> mp_vec; 형태로 선언하고, vector<int> vec(MAX, 0)에는 현재 부분 문자열에 포함된 26개 알파벳 각각의 빈도수가 저장됩니다. 맵에 매핑된 정수 값은 동일한 빈도 벡터를 가진 부분 문자열의 개수를 의미합니다.

어떤 빈도 벡터에 해당하는 아나그램 부분 문자열이 x개 있다면, 만들 수 있는 아나그램 쌍의 총 개수는 조합 공식에 따라 x * (x-1) / 2가 됩니다.

알고리즘 단계

문자열 str[]을 문자 배열로 받습니다.
anagram_substring(string str, int length) 함수가 문자열을 받아 아나그램 부분 문자열의 총 개수를 반환합니다.
초기 카운트(count)를 0으로 설정합니다.
맵 map<vector<int>, int> mp_vec; 를 선언합니다.
두 개의 for 반복문(i=0부터 i<length까지, j=i부터 j<length까지)으로 str[]을 순회합니다.
각 부분 문자열 str[i~j]에 대해 vector<int> vec(MAX, 0); 가 포함된 영어 알파벳의 개수를 저장합니다.
현재 문자 c를 str[j]로 가져오고, temp = c - 'a' 로 정수값을 계산합니다.
vec[temp]++ 로 해당 알파벳의 빈도를 갱신합니다.
mp_vec[vec]++ 로 이 빈도 벡터에 대응하는 카운트를 증가시킵니다.
모든 빈도 벡터가 저장된 맵을 반복자 it = mp_vec.begin()부터 it != mp_vec.end()까지 순회하며 부분 문자열 개수를 집계합니다.
각 항목의 개수(it->second)를 last라고 할 때, 모든 아나그램 쌍을 위해 ((last) * (last-1)) / 2 를 count에 더합니다.
최종적으로 모든 아나그램의 개수가 count에 누적됩니다.
count를 결과로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
#define MAX 26
int anagram_substring(string str, int length){
    int count = 0;
    map<vector<int>, int> mp_vec;
    for (int i=0; i<length; i++){
        vector<int> vec(MAX, 0);
        for (int j=i; j<length; j++){
            char c = str[j];
            char temp = c - 'a';
            vec[temp]++;
            mp_vec[vec]++;
        }
    }
    for (auto it = mp_vec.begin(); it != mp_vec.end(); it++){
        int last = it->second;
        count += ((last) * (last-1))/2;
    }
    return count;
}
int main(){
    string str = "TP";
    int length = str.length();
    cout<<"Count of total anagram substrings are: "<<anagram_substring(str, length) << endl;
    return 0;
}

실행 결과

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

Count of total anagram substrings are: 3

이 방법은 시간 복잡도가 O(n²)인 부분 문자열 탐색에 추가로 맵 연산 비용이 들지만, 문자 빈도 벡터를 키로 사용하면 문자 순서와 무관하게 아나그램 여부를 정확히 판별할 수 있다는 장점이 있습니다.