[백준] 팰린드롬 만들기

[백준] 팰린드롬 만들기

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

• 유의할 테스트케이스

input: AAABB
answer: ABABA

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

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

	string name;
	cin >> name;
	int nameLen = name.length();

	if (nameLen == 1) {
		cout << name;
		return 0;
	}

	//name에 각 알파벳이 몇 번 나왔는지 저장
	//ex. alphabet['A'-65] = A가 name에 나오는 횟수
	vector<int> alphabetCnt(26, 0);
	for (int i = 0; i < nameLen; ++i) {
		alphabetCnt[name[i] - 65]++;
	}

	//팰린드롬을 만들 때 사용할 알파벳들의 아스키코드
	vector<int> alphabets;

	//팰린드롬 문자열
	string pldr = "";

	if ((nameLen % 2) == 0) {
		//이름의 길이 짝수인 경우
		//모든 알파벳 짝수 개 있어야 팰린드롬 가능
		bool flag = true;
		for (int i = 0; i < 26; ++i) {
			if ((alphabetCnt[i] % 2)==0){
				//2n번 나타난 알파벳 -> alpabets에 n번 저장
				for (int j = 0; j < alphabetCnt[i]; j += 2) {
					alphabets.push_back(65 + i);
				}
			}
			else {
				flag = false;
				break;
			}
		}
		if (!flag) {
			cout << "I'm Sorry Hansoo";
			return 0;
		}

		//사전순으로 제일 앞서는 팰린드롬 만들기 위해 정렬
		sort(alphabets.begin(), alphabets.end());
		for (int i = 0; i < alphabets.size(); ++i) {
			pldr += char(alphabets[i]);
		}
		//팰린드롬 만들기
		reverse(alphabets.begin(), alphabets.end());
		for (int i = 0; i < alphabets.size(); ++i) {
			pldr += char(alphabets[i]);
		}

		cout << pldr;
	}
	else {
		//이름의 길이 홀수인 경우
		//홀수 번 나타나는 알파벳 하나 존재
		//나머지 알파벳들은 짝수 번 존재
		bool flag = true;
		int solo = -1; //1번 나타나는 알파벳의 아스키코드
		for (int i = 0; i < 26; ++i) {
			if ((alphabetCnt[i] % 2)==0) {
				//2n번 나타난 알파벳 -> alpabets에 n번 저장
				for (int j = 0; j < alphabetCnt[i]; j += 2) {
					alphabets.push_back(65 + i);
				}
			}
			else if (solo == -1) {
				//2n+1번 나타난 알파벳 -> alpabets에 n번 저장
				for (int j = 0; j < alphabetCnt[i]-1; j += 2) {
					alphabets.push_back(65 + i);
				}
				solo = 65 + i;
			}
			else {
				flag = false;
				break;
			}
		}
		if ((!flag) || (solo == -1)) {
			cout << "I'm Sorry Hansoo";
			return 0;
		}

		//사전순으로 제일 앞서는 팰린드롬 만들기 위해 정렬
		sort(alphabets.begin(), alphabets.end());
		for (int i = 0; i < alphabets.size(); ++i) {
			pldr += char(alphabets[i]);
		}
		//홀수 번 나타난 알파벳 팰린드롬 정가운데에 위치
		pldr += char(solo);
		//팰린드롬 만들기
		reverse(alphabets.begin(), alphabets.end());
		for (int i = 0; i < alphabets.size(); ++i) {
			pldr += char(alphabets[i]);
		}

		cout << pldr;

	}
	return 0;
}