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

문제 https://www.acmicpc.net/problem/1213

 

 

풀이

 

입력받은 알파벳들의 개수를 세서, 대칭이 맞도록 출력한다.

대칭이 되려면 홀수개의 알파벳이 최대 1개만 있어야 하므로 (ABA, AABAA...) 만약 홀수개의 알파벳이 2개 이상이 된다면 "I'm Sorry Hansoo"를 출력한다.

 

정답이 여러 개일 경우 사전 순으로 앞서는 것을 출력해야 하므로, A부터 시작해서 대칭을 만들면 된다.

반쪽을 먼저 만든 후, 만약 홀수개의 알파벳이 있다면 출력한 후, 나머지 반쪽을 만들면 팰린드롬으로 만들 수 있다.

 

코드

#include <string>
#include <iostream>
using namespace std;

string ans;
int alpha[26];
int main()
{
    string s;
    cin>>s;

    for(int i=0; i<s.length(); i++)
    {
        alpha[s[i]-'A']++;
    }

    int cnt=0;
    for(int i=0; i<26; i++)
    {
        if(alpha[i]%2==1) cnt++;
    }
    if(cnt>1) 
    {
        cout<<"I'm Sorry Hansoo";
        return 0;
    }

    for(int i=0; i<26; i++)
    {
        for(int j=0; j<alpha[i]/2; j++)
        {
            ans+=i+'A';
        }
    }
    for(int i=0; i<26; i++)
    {
        if(alpha[i]%2==1) ans+=i+'A';
    }
    for(int i=25; i>=0; i--)
    {
        for(int j=0; j<alpha[i]/2; j++)
        {
            ans+=i+'A';
        }
    }
    cout<<ans;
}