[1213] 팰린드롬 만들기

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

1213번: 팰린드롬 만들기

<문제>

불가능한 경우를 먼저 생각해보자. 

"홀수개만큼 등장한 알파벳이 2개 이상인 경우"를 불가능한 경우로 잡고 풀었다.

AA, ABBA, ABCCBA처럼 항상 짝수개라면 당연히 절반씩 나누어 만들수 있으며

1개까지는 ABA, ABCBA, ABCDCBA처럼 정가운데에 끼워넣어서 커버할 수 있다.

꼭 한개가 아니라 3개나 5개도 ABBBA나 ABCCCCCBA처럼 가능하므로 모든 홀수로 확장이 가능하다.

 

각 문자가 등장한 횟수를 카운트해주고, "%2==1"인 순간이 2회가 되는순간 바로 "I'm Sorry Hansoo"를 출력후 종료.

한번이라면 해당 문자를 저장해준다.(코드에선 char mid에 저장했다)

 

사전순으로 오름차순을 찾아야 하는데 이 부분은 아래과정중 자동으로 처리된다.

-> A부터 시작해서 Z까지 나온횟수 / 2만큼 출력

-> 정가운데 들어갈 문자가 있다면, 출력

-> Z부터 시작해서 A까지 나온횟수 / 2만큼 출력

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
vector<int> a(27);
int main(void) {
    string s;
    cin >> s;
    int i, j, n = s.length();
    for (i = 0; i < n; i++) a[s[i] - 'A']++;
    char mid = 0;
    vector<char> ans;
    for (i = 0; i < 26; i++) {
        if (a[i] % 2 == 1 && mid == 0) {
            mid = (char)'A' + i;
            goto skip;
        }
        if (a[i] % 2 == 1) {
            cout << "I'm Sorry Hansoo";
            return 0;
        }
    skip:
        for (j = 0; j < a[i] / 2; j++) ans.push_back('A' + i);
    }
    for (auto i = ans.begin(); i < ans.end(); i++) {
        cout << *i;
    }
    if (mid != 0) cout << mid;
    for (auto i = ans.rbegin(); i < ans.rend(); i++) {
        cout << *i;
    }
    return 0;
}