[ 백준 1213 ] 팰린드롬 만들기 (C++)

백준의 팰린드롬 만들기(1213) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 사실, 본인은 이 문제를 처음 풀 때, 입력으로 주어진 문자들로 나올 수 있는 모든 순열을 모두 구현해서 팰린드롬인지 아닌지

   판단 후, 맞다면 출력하는 식으로 구현하였다. 하지만, 시간초과를 받았다.

   따라서, 이 문제는 순열로 모든 경우를 구하는 것이 아니라, 다른 방법으로 구해줘야 한다.

   먼저, 모든 문자열은 팰린드롬이 가능한지 부터 따져보자.

   "AABB", "AABBC", "AABBCC", "AABBCD" 4개의 문자열이 있다. 앞에서 부터 1,2,3,4 번이라고 생각하자.

   1번은 팰린드롬 문자열이다. "ABBA" 이 되기 때문이다.

   2번도 팰린드롬 문자열이다. "ABCBA"가 되기 때문이다.

   3번도 팰린드롬 문자열이다. "ABCCBA"가 되기 때문이다.

   4번은 팰린드롬 문자열이 될 수가 없다.

   잘보면, 홀수개인 알파벳이 2개 이상이면 팰린드롬 문자열이 될 수 없다는 것을 알 수 있다.

   1번의 경우 홀수개인 알파벳 = 0개. (A도 2개, B도 2개)

   2번의 경우 홀수개인 알파벳 = 1개. (A 2개, B 2개, C 1개)

   3번의 경우 홀수개인 알파벳 = 0개 , 4번의 경우 홀수개인 알파벳 = 2개 (A 2개, B 2개, C 1개, D 1개)

   즉, 팰린드롬 문자열이 되기 위해서는 문자열속에 존재하는 모든 알파벳이 짝수개 있거나, 홀수개 존재하는 알파벳이 한 개만

   존재해야 한다. 2개 이상이라면 팰린드롬 문자열이 될 수가 없다.

   따라서 본인은 입력과 동시에, 문자열 속에 존재하는 알파벳의 갯수를 Count해 주었다. 이 후, 홀수인 알파벳에 대해서는

   총 몇개인지 , 홀수인 알파벳을 따로 저장 해주었다.

   홀수인 알파벳을 따로 저장해준 이유는, 위에서 봤듯이, 홀수개인 알파벳이 1개라면 계산이 가능하기 때문에 따로 저장해 주었

   다. 만약, 그 전에 이미 홀수인 알파벳이 2개 이상이라면 바로 Sorry Hansoo 를 출력해주고 끝내주었다.

2) 본격적인 팰린드롬 문자열을 만드는 과정은 모든 알파벳이 짝수개로만 이루어져있거나, 혹은 홀수개인 알파벳이 하나 있거나

   크게 2개로 나뉘어진다.

   모든 알파벳이 짝수인 경우에는 모든 알파벳들을 앞에서 부터 순서대로 절반개만 뽑아주고, 뒤집어서 합쳐주면 된다.

   문제에서 "사전순으로 앞서는 것을 출력해라" 라는 조건이 있다. 위에서, 알파벳의 갯수를 Count한다고 했는데, 이를

   Alphabet[26] 이라는 1차원 배열에 갯수를 저장해 두었다. 즉 A가 2개 있다면 Alphabet[0] = 2가 된다.

   사전순으로 출력해야 하기 때문에, 0 ~ 26 까지 for문을 돌리면서, 나오는 알파벳들을 절반개를 먼저 출력한다.

   예를 들어서, AABB가 있다고 가정해보자. A = 2개, B = 2개 이다. 먼저, A부터 절반개인 1개를 출력한다.

   그리고, 이 다음 나오는 B를 절반개인 1개를 출력해서 합치면 AB가 된다. 이를 뒤집어서 붙여주면 ABBA 라는 팰린드롬 문자열

   중에서 가장 앞서는 정답이 나오게 된다.

  

   다음은 홀수개인 알파벳이 하나 있을 경우이다. 예를 들어서 AAABB가 있다고 생각해보자. 이를 팰린드롬 문자열을 만들면

   ABABA가 나오게된다. 즉, AB + 홀수개인 문자 + AB를 뒤집은 형태 가 된다.

   전체적인 풀이는 위에 모든 알파벳이 짝수인 경우와 똑같은데, 마지막 합쳐줄 때,

   가운데 홀수개인 문자를 하나 넣어줘야 한다. 즉, 절반개 출력해서 "AB"를 만들고, 뒤집은 "BA"를 만들고

   AB + 위에서 따로 저장해둔 홀수개인 알파벳 + BA 이런 식으로 답을 도출하면 된다.

   설명은 이해가 잘 안될지 몰라도 소스코드를 본다면 이해가 될 것이다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
string Inp;
int Len, Odd_Cnt, Odd_Idx;
char Odd_Char;
int Alphabet[26];
bool Select[MAX];
 
vector<char> V;
 
void Input()
{
    cin >> Inp;
    Len = Inp.length();
    for (int i = 0; i < Len; i++)
    {
        int Temp = Inp[i] - 'A';
        Alphabet[Temp]++;
    }
 
    for (int i = 0; i < 26; i++)
    {
        if (Alphabet[i] == 0) continue;
        if (Alphabet[i] % 2 == 1)
        {
            Odd_Cnt++;
            Odd_Char = i + 'A';
        }
    }
 
    if (Odd_Cnt >= 2)
    {
        cout << "I'm Sorry Hansoo" << endl;
        exit(0);
    }
}
 
bool Sorting_Standard(int A, int B)
{
    if (A > B) return true;
    return false;
}
 
void Solution()
{
    string Answer = "";
    string Reverse_Answer = "";
    string Temp;
 
    if (Odd_Cnt == 0)    // 모든 알파벳이 짝수인 경우
    {
        for (int i = 0; i < 26; i++)
        {
            if (Alphabet[i] == 0) continue;
            int Half = Alphabet[i] / 2;
 
            for (int j = 0; j < Alphabet[i] / 2; j++)
            {
                Answer = Answer + char(i + 'A');
            }
        }
 
        Temp = Answer;
        reverse(Temp.begin(), Temp.end());
        Reverse_Answer = Temp;
 
        Answer = Answer + Reverse_Answer;
        cout << Answer << endl;
    }
    else
    {
        for (int i = 0; i < 26; i++)
        {
            if (Alphabet[i] == 0) continue;
            int Half = Alphabet[i] / 2;
 
            for (int j = 0; j < Alphabet[i] / 2; j++)
            {
                Answer = Answer + char(i + 'A');
            }
        }
 
        Temp = Answer;
        reverse(Temp.begin(), Temp.end());
        Answer = Answer + Odd_Char;
        Answer = Answer + Temp;
        cout << Answer << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}