시작

이 문제는 상당히 어렵다, 순열인 next_permutation을 사용해 풀어보니, 시간초과가 뜨며, 다시 풀어보니 틀렸다고 뜨니, 꽤나 멘붕이 오면서 풀었다. 그렇다면 한번 조건을 먼저 살펴보자.

조건

1. 홀수인 알파멧의 종류가 2개 이상이면 안됨
2. 무조건 펠린드롬이 완성되야됨.

이런 조건들이 있는데, 1번의 조건을 확인해보면 홀수인 알파벳의 종류가 2개이면 안되는 이유를 살펴보자.
우선 예시로, AABC가 있다고 가정하자. 그렇다면 ABCA로 만들어도 안되며, ABAC...들이 나오는데, 아무리 해도 펠린드롬이 안되는 것이다. 예시로 든 AABC는 A는 2개 B는 1개 C는 1개다. 그러면 B와 C는 홀수여서 안되는 것이라 볼 수 있는데, 마찬가지로 개수가 홀수인 알파벳이 3개, 4개, ..이 되어도, 펠린드롬이 안된다는 것을 알 수 있다.

코드

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string s, ret;
	int cnt[201] = {0, }, flag = 0;
	char mid;
	cin >> s;
	// 알파벳 종류의 개수 확인
	for (char c : s) cnt[c]++;
	for (int i = 'Z'; i >= 'A'; i--) {
		// 만약 있다면
		if (cnt[i]) {
			// 홀수면 flag +1
			if (cnt[i] & 1) {
				mid = char(i); flag++;
				cnt[i]--;
			}
			// 홀수가 2개 이상이면 끝내기
			if (flag == 2) break;
			// 두개씩 넣으면서 펠린드롬 만들기
			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);
	// flag가 두개면 못만듬
	if (flag == 2) cout << "I'm Sorry Hansoo";
	else {
		cout << ret << "\n";
	}
}