[BOJ 1213] 펠린드롬 만들기

문제출처

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

문제풀이

/**
 * 1. 홀수개인 알파벳이 2개 이상이라면 펠린드롬을 만들 수 없음,
 * 2. 짝수개인 알파벳을 n/2개 나열하고 홀수개인 알파벳을 나열한 후
 *    나머지 짝수개 알파벳을 역순으로 나열하면 펠린드롬이 생성
 *    
 * 정리하면 input 길이가 홀수라면 홀수개인 알파벳이 1개여야 하며,
 * input 길이가 짝수라면 모든 알파벳의 갯수도 짝수개여야 한다.
 * 이 조건을 통과하면 사전순으로 출력하는 문제이다. a~z까지 n/2개씩 출력하고
 * 거꾸로 z~a까지 절반을 출력하면 사전순으로 출력된다.
 */

소스코드

#include <iostream>
#include <string>
 
using namespace std;
 
int alpha[26];
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string input,answer="";
    cin>>input;
    int len = input.size();
    for(int i=0; i<len; i++) alpha[input[i]-'A']++;
    int oddCnt=0, center=-1;
    for(int i=0; i<26; i++) {
        if(alpha[i]%2) {
            oddCnt++;
            center=i;
        }
    }
    if((len%2 && oddCnt!=1) || (!(len%2) && oddCnt)) {
        cout<<"I'm Sorry Hansoo";
        return 0;
    }
 
    for(int i=0; i<26; i++)
        for(int j=0; j<alpha[i]/2; j++)
            answer+=(char)i+'A';
 
    if(center>-1) answer+=(char)center+'A';
 
    for(int i=25; i>=0; i--)
        for(int j=0; j<alpha[i]/2; j++)
            answer+=(char)i+'A';
 
    cout<<answer;
    return 0;
}