[SWEA 3816] 아나그램 - C++

SW Expert Academy

문제

아나그램이란 문자열의 문자들을 모두 사용하여 재배열한 것을 의미한다.
“abc”의 아나그램은 “abc”, “acb”, “bac”, “bca”, “cab”, “cba” 총 6개이다.
문자열 S1, S2이 차례대로 주어진다. S2의 부분문자열 중 S1의 아나그램인 것의 개수를 구하는 프로그램을 작성하라.

입력

첫 줄에 테스트케이스의 개수 T가 주어진다. (T ≤ 20)
각 테스트케이스의 첫 줄에 S1, S2가 사이에 공백을 갖고 띄어져 있다.
S1과 S2는 영문 소문자로만 이루어져 있다. (1 ≤ |S1| ≤ |S2| ≤ 100,000)(|S1|, |S2|는 문자열 S1, S2의 길이)

풀이

int isEqual(int* s1_counter, int* s2_counter)
{
    for (int i = 0; i < 26; i++)
    {
        if (s1_counter[i] != s2_counter[i])
        {
            return 0;
        }
    }
    return 1;
}
 
int FindAnagram(int Len1, char *S1, int Len2, char *S2) {
    int answer = 0;
    int s1_counter[26] = { 0 };
    int s2_counter[26] = { 0 };
    //S1 기록
    for (int i = 0; i < Len1; i++)
    {
        int temp;
        temp = int(S1[i] - 'a');
        s1_counter[temp] += 1;
    }
    for (int i = 0; i < Len1; i++)
    {
        int temp;
        temp = int(S2[i] - 'a');
        s2_counter[temp] += 1;
    }
    answer += isEqual(s1_counter, s2_counter);
    for (int i = Len1; i < Len2; i++)
    {
        int temp;
        temp = int(S2[i - Len1] - 'a');
        s2_counter[temp] -= 1;
        temp = int(S2[i] - 'a');
        s2_counter[temp] += 1;
        answer += isEqual(s1_counter, s2_counter);
    }
    return answer;
}

해결방법

S1의 문자열 길이를 기준으로 각 알파벳에 대한 카운터를 운영하여 한칸씩 이동하면서 동일한 알파벳 수를 가지고 있는지 확인하면 되는 문제입니다.