[BOJ 1213] 팰린드롬 만들기(브루트 포스 접근이 필요한가?)

팰린드롬은 알고리즘의 단골 소재이다.

 

 

 

이번 문제는, 팰린드롬을 만들어야 하는 문제이다.

 

 

 

팰린드롬은, 문자열를 뒤집어도 같은 문자열이 되어야 한다.

 

 

 

주어진 문자열을 통해서, 각 대문자 알파벳의 개수를 파악하고 짝수냐 홀수에 따라서 문자열을 처리해주면 된다.

 

 

 

팰린드롬이 불가능한 경우는, 홀수인 알파벳이 1개 초과되면 팰린드롬이 불가능하게 된다.

 

 

 

위의 말들을 바탕으로 코드를 구현하면 아래와 같다.

 

 

 

해설코드(C++).

#include <iostream>
#include <string>
 
using namespace std;
int arr[26] = { 0 };
 
string s;
char c = ' ';
 
int main() {
    cin >> s;
    bool odd = true;
    for(int i = 0; i < s.length(); i++){
        arr[s[i] - 'A'] += 1;
    }
 
    s = "";    
    for(int i = 0; i < 26; i++){
        if(arr[i] % 2 != 0){
            if(odd){
                odd = false;
                c = i + 'A';
            }else{
                cout << "I'm Sorry Hansoo" << endl;
                return 0;
            }
        }
        
        for(int j = 1; j <= arr[i] / 2; j++) s += ('A' + i);
    }
    
    int len = s.length();
    if(c != ' ') s += c;
    
    for(int i = len - 1; i >= 0; i--)
        s += s[i];
        
    cout << s << endl;
    return 0;
}