문제

문제링크

해설

• 우선 팰린드롬이 ‘절대 만들어질 수 없는 조건’을 파악합니다.
  • 홀수번 등장하는 알파벳이 2개 이상이면 팰린드롬을 만들 수 없습니다.
• 팰린드롬의 구조는 다음 두 가지 중 하나입니다.
  • 홀수번 등장한 알파벳이 0개: (prefix) + (뒤집힌 prefix)
  • 홀수번 등장한 알파벳이 1개: (prefix) + (그 알파벳 × 홀수번) + (뒤집힌 prefix)
• 사전순으로 우선적으로 등장하는 팰린드롬을 만들기 위해서는
  • 주어진 문자열을 순차적으로 읽으면서 알파벳 등장 횟수를 검사합니다.
  • ‘0’번 인덱스부터 읽으면서 ‘2로 나눈 몫’ 개수만큼 prefix 문자열에 붙입니다.
    • e.g) B가 2번 등장했다면, prefix에 B를 1개 덧붙이고,
    • e.g) B가 6번 등장했다면, prefix에 B를 3개 덧붙입니다.

코드

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

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    string name;
    cin >> name;

    int alpha[26] = {0, };
    for (const char& ch : name) alpha[ch - 'A']++;

    int odd_number = 0, odd_number_count = 0;
    for (int i = 0; i < 26; i++) {
        if (alpha[i] & 1) {
            odd_number_count++;
            odd_number = i;
        }
    }
    // Can't build palindrome if there's over 2 numbers oddly advented.
    if (odd_number_count >= 2) {
        cout << "I'm Sorry Hansoo\n";
        exit(0);
    }
    // Build prefix of palindrome
    string prefix = "";
    for (int i = 0; i < 26; i++) {
        int loop = alpha[i] / 2;
        for (int j = 0; j < loop; j++) prefix += static_cast<char>('A' + i);
    }
    // Build subfix of palindrome by reverse_copy()
    string subfix(prefix.length(), 0);
    reverse_copy(cbegin(prefix), cend(prefix), begin(subfix));
    
    // If there is a number which appeared oddly, it should be pushed to prefix.
    if (odd_number_count > 0) prefix += static_cast<char>('A' + odd_number);

    cout << prefix + subfix << '\n';
    return 0;
}

결과