본인 코드

#include <bits/stdc++.h>
using namespace std;
string s;
map<string, int> mp;

// 팰린드롬 확인 후 맵에 저장 - 중복순열 방지
void isPalindrome(string input){
    for (int i = 0; i < input.length() / 2; i++){
        if(input[i] == input[input.length() -1 - i]){
            continue;
        }else{
            return;
        }
    }
    if(mp[input]){
        return;
    }else{
        mp[input] = 1;
    }
}

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

    cin >> s;
    vector<int> idx;


    // 1. 문자열 자체로도 순열 적용이 가능하지만 중복순열은 무시함. -> 인덱스 배열 생성해서 순열 적용
    for (int i = 0; i < s.size(); i++){
        idx.push_back(i);
    }
    do{
        string newstring;
        for (int i : idx){
            newstring += s[i];
        }

        isPalindrome(newstring);
    } while (next_permutation(idx.begin(), idx.end()));

    if(mp.size() == 0){
        cout << "I'm Sorry Hansoo"
             << "\n";
        return 0;
    }

    // 사전순서 판단 - 사전순 가장 첫번째 요소를 어떻게 선택할지
    int count = 0;
    string cmp;
    for (auto it : mp){
        if(count == 0){
            cmp = it.first;
            count++;
        }else{
            // 다른 문자열 배치가 사전순으로 더 앞선 경우
            if(cmp > it.first){
                cmp = it.first;
            }else{
                continue;
            }
        }
    }
    cout << cmp << "\n";
    return 0;
}

1. 순열배치 과정에서 시간초과가 발생하였음. 그도 그럴것이 n! / (n-r)!일때 차수가 매우 커지기 때문이다.

개선 코드

1. 반복되는 문자가 홀수개인 집단이 둘 이상이면 팰린드롬이 만들어지지 않는다. Ex) ABBC
2. 팰린드롬 문자열 집합을 사전순 오름차순 배치를 위해서는 사전적으로 가장 뒷순위 문자를 가장 가운데에 모아 배치해야한다.
3. 어차피 홀수개 문자는 팰린드롬 내에서 한번만 등장하므로 짝수개 오름차순 배치 후 남은 한 문자는 가장 가운데에 배치해야만 한다.

로직 이해 후 다시 짠 코드 - 정답처리됨

#include <bits/stdc++.h>
using namespace std;
string s;

// A 몇개, B 몇개 ..
map<char, int> mp;

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

    cin >> s;
    for(char chr : s){
        if(mp[chr]){
            mp[chr] += 1;
        }else{
            mp[chr] = 1;
        }
    }

    // 반복되는 문자가 홀수개인 집단이 둘 이상이면 팰린드롬이 만들어지지 않는다.
    // 홀수개의 문자는 하나뿐이라는 뜻 -> 가운데에 삽입하면 됨
    int odd_count = 0;

    // 알파벳 맵 키값 저장을 위한 벡터
    vector<char> v;

    for (auto it : mp){
        v.push_back(it.first);
        if (it.second % 2 == 1)
        {
            odd_count += 1;
        }
    }
    if(odd_count >= 2){
        cout << "I'm Sorry Hansoo" << "\n";
        return 0;
    }

    // 문자열 오름차순으로 반만 만들고 나머지는 reverse해서 붙인다.
    string newstring;
    string result, remain;
    sort(v.begin(), v.end());
    for (auto it : mp)
    {
        if(it.second % 2 == 1){
            remain += it.first;
        }
        for (int i = 0; i < it.second / 2; i++){
            newstring += it.first;
        }
    }

    result += newstring;
    if(remain.length() != 0){
        result += remain;
    }
    reverse(newstring.begin(), newstring.end());
    result += newstring;

    cout << result << "\n";

    return 0;
}

아래는 모범답안이다.

#include <bits/stdc++.h>
using namespace std;
string s, ret;
int cnt[200], flag;
char mid;

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

    cin >> s;
    // 알파벳 카운팅 배열
    for(char a : s){
        cnt[a]++;
    }

    // 오름차순 지정은 for문 시작부터 이미 되어있음
    for (int i = 'Z'; i >= 'A'; i--){
        if(cnt[i]){
            // 홀수 비트연산자
            // flag는 홀수개인 문자의 개수 - 둘 이상이면 탈출
            if(cnt[i] & 1){
                mid = char(i);
                flag++;

                // mid문자 제외하고 나머지는 앞뒤로 짝수개 붙임
                cnt[i]--;
            }
            if(flag == 2){
                break;
            }

            // 앞뒤로 두개를 소모하므로 += 2가 됨.
            for (int j = 0; j < cnt[i]; j += 2){
                ret = char(i) + ret;
                ret += char(i);
            }
        }
    }

    // 홀수문자 삽입
    if(mid){
        ret.insert(ret.begin() + ret.size() / 2, mid);
    }

    if(flag == 2){
        cout << "I'm Sorry Hansoo\n";
    }else{
        cout << ret << "\n";
    }
    return 0;
}