[ SWEA 4672 ] 수진이의 팰린드롬 (C++)

SWExpertAcademy의 수진이의 팰린드롬(4672) 문제이다.

[ 문제풀이 ]

1) 주어진 문자열을 재구성하였을 때 팰린드롬 문자열의 최대 갯수를 출력하는 것이 문제이다.

    본인은 '같은 문자끼리 무조건 붙이는 방법' 으로 구현해 보았다.

    왜 같은 문자끼리 붙이는 방법이 최대의 팰린드롬 문자열의 갯수를 도출해 낼 수 있을까??

    사실 본인도 이에 대한 정확한 계산은 하지 못했지만 다음과 같이 생각해서 이 방법을 택해보았다.

    문자열 중에 어떤 문자를 택해서 팰린드롬을 만들 때, 그 문자에서 나올 수 있는 팰린드롬의 갯수를 모두 사용하지 않으면

    과연 최대의 갯수가 나올 수 있을까? 라는 생각이 들었다.

    예를 들어서 어떤 한 문자열의 'a'의 갯수를 Count해보니 2개가 나왓다고 가정해보자.

    이 때, "aa"로 우리는 'a', 'a', 'aa' 라는 최대 3개의 팰린드롬 문자열을 만들 수가 있다. 이 경우는 'a'2개가 붙어 있는 경우에

    최대가 된다. 그렇다면, 'a' 2개를 각자 떨어뜨려놓고 계산을 하게 된다면 과연 최대가 나올 수 있을까 ??

    물론 똑같은 최댓값이 나올 수는 있지만, 붙여놨을 때 보다 더 큰 값이 나오지는 않을 것이라 생각했다.

    따라서 본인은 이와 같은 방법을 선택했고, 실제로 제출해보니 pass를 받을 수 있었다.

    따라서 먼저 계산을 하기전 주어진 문자열에서 각각의 문자들의 갯수를 구해보았다.

    그렇다면 주어진 갯수들을 통해서 어떤 식을 도출해 냈는지 알아보자.

    예를 들어서 "a" 1개만 존재하는 문자열이 있을 때, 팰린드롬 문자열의 갯수는 1개이다.

    "aa"가 있다면, 아마 'a', 'a', 'aa' 로 총 3개의 팰린드롬 문자열이 존재하게 될 것이다.

    "aaa"가 있다면, 아마 'a', 'a', 'a', 'aa', 'aa', 'aaa' 로 6개가 나오게 된다.

    그렇다면 우리는 여기서 규칙을 하나 알 수가 있다.

    특정 문자가 1개 = 1개의 팰린드롬 문자열 생성

    2개 = 3개의 팰린드롬 문자열 생성

    3개 = 6개의 팰린드롬 문자열 생성

    즉, 특정 문자가 A개 있으면 나올 수 있는 팰린드롬 문자열의 갯수는 (A x (A + 1)) / 2 가 된다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
 
#define endl "\n"
using namespace std;
 
string Inp;
int Cnt[26];
int Answer;
 
bool Sort_Standard(int A, int B)
{
    if (A > B) return true;
    return false;
}
 
void Initialize()
{
    Answer = 0;
    memset(Cnt, 0, sizeof(Cnt));
    Inp.clear();
}
 
void Input()
{
    cin >> Inp;
}
 
void Solution()
{
    for (int i = 0; i < Inp.length(); i++)
    {
        Cnt[Inp[i] - 'a']++;
    }
    sort(Cnt, Cnt + 26, Sort_Standard);
 
 
    for (int i = 0; i < 26; i++)
    {
        if (Cnt[i] == 0) break;
        Answer = Answer + ((Cnt[i] * (Cnt[i] + 1)) / 2);
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}