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

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

1213번: 팰린드롬 만들기

---

Solved By: Implementation

 

백트래킹으로 풀어야 할 거 같았는데 구현도 될 거 같아서 한 번 해보았습니다.

알파벳의 개수를 세고, 특정 알파벳의 개수가 홀수인 경우가 아예 없거나 한 번인 경우만 팰린드롬이 만들어지기 때문에 여기서 첫 조건 분기를 해줍니다.

 

그다음 A부터 순차적으로 문자열을 쌓는 식으로 만들 겁니다. 순차적으로 쌓다가 홀수개의 알파벳이 있는 경우 어떤 알파벳인지 확인해둡니다. 순차적으로 쌓는 게 끝난 경우, 홀수 개의 알파벳이 있다면 '순차적 문자열 + 홀수 개의 알파벳 + 순차적 문자열 뒤집은 문자열'로 결괏값을 출력하고, 없다면 '순차적 문자열 + 순차적 문자열 뒤집은 문자열'로 출력해주면 됩니다.

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

int cnt_alpha[26];

int main(){
    string s; cin >> s;
    for(int i = 0; i < s.length(); i++){
        cnt_alpha[s[i] - 'A']++;
    }
    
    int is_odd = 0;
    for(int i = 0; i < 26; i++){
        if(cnt_alpha[i] % 2) is_odd++;
    }
    
    if(is_odd > 1) cout << "I'm Sorry Hansoo";
    else{
        string ans = "";
        int odd_idx = -1;
        for(int i = 0; i < 26; i++){
            if(cnt_alpha[i] % 2 == 0){
                for(int j = 0; j < cnt_alpha[i] / 2; j++){
                    ans += (i + 'A');
                }
            }
            else{
                for(int j = 0; j < cnt_alpha[i] / 2; j++){
                    ans += (i + 'A');
                }
                odd_idx = i;
            }
        }
        
        string ans_temp = ans;
        reverse(ans.begin(), ans.end());
        if(odd_idx != -1){
            ans = ans_temp + (char)(odd_idx + 'A') + ans;
        }
        else{
            ans = ans_temp + ans;
        }
        cout << ans;
    }
}