[백준 1213] 팰린드롬 만들기 (C++)

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

문제

---

임한수와 임문빈은 서로 사랑하는 사이이다.

임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.

임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.

임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다.

 

출력

---

첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.

 

문제 풀이

---

그리디 문제.

 

팰린드롬은 앞에서부터 읽는 것과 뒤에서부터 읽는 문자의 순서가 같다. 따라서 문자열이 팰린드롬을 이루려면 앞에서부터 1번째 문자와 뒤에서 1번째 문자가 같아야 하고, 앞에서부터 2번째 문자와 뒤에서 2번째 문자가 같아야 하는 방식을 문자열 중간까지 취해야 한다.

따라서 문자열의 길이가 짝수일 경우, 모든 문자가 나타나는 횟수는 짝수여야 한다. 문자열의 길이가 홀수인 경우, 가운데에 있을 문자로 인하여 단 하나의 문자만 홀수이고, 나머지는 짝수이다.

 

문자열을 입력받아 각 알파벳 별로 문자가 몇 번 나타나는지 구한다. 사전 순으로 앞서는 것을 출력하기 위해 짝수 번 나타나는 큐 even과 홀수 번 나타나는 큐 odd를 만들어 해당하는 큐에 알파벳과 문자가 나타나는 횟수를 저장하여 답을 구한다. 위에서 설명한대로 문자열의 길이가 짝수라면 odd에는 원소가 없어야 한다. 문자열의 길이가 홀수라면 odd에는 한 가지의 원소만 있어야 한다. 이 조건을 충족했다면 팰린드롬을 만들 수 있다.

even에서 원소를 순서대로 꺼내어 문자열의 앞부분을 만들고, reverse()를 이용하여 거꾸로 된 문자열을 만들어 두 문자열을 이어 붙이면 된다.

문자열의 길이가 홀수일 때에는 odd에 있는 알파벳이 even의 front에 있는 알파벳보다 사전 순으로 앞설 수 있으므로 매번 확인하여 odd에 있는 알파벳을 정답 문자열에 붙일지, even에 있는 알파벳을 정답 문자열에 붙일지 판단해주면 된다. 그리고 마찬가지로 reverse()를 이용하여 거꾸로 된 문자열을 만들어 두 문자열을 이어 붙이면 된다.

 

아래는 코드.

#include <iostream>
#include <queue>
#include <utility>
#include <string>
#include <algorithm>
using namespace std;

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

	string str;
	cin >> str;
	int N = str.length();
	int* counts = new int[26];
	queue<pair<char, int>> even;
	queue<pair<char, int>> odd;
	string answer = "";
	for (int i = 0; i < 26; i++)
	{
		counts[i] = 0;
	}
	for (int i = 0; i < N; i++)
	{
		int index = str.at(i) - 65;
		counts[index]++;
	}
	for (int i = 0; i < 26; i++)
	{
		if (counts[i] % 2 == 0 && counts[i] != 0)
		{
			even.push(pair('A' + i, counts[i]));
		}
		else if (counts[i] % 2 != 0)
		{
			odd.push(pair('A' + i, counts[i]));
		}
	}
	if (N % 2 == 0)
	{
		if (odd.size() != 0)
		{
			cout << "I'm Sorry Hansoo" << "\n";
		}
		else
		{
			while (!even.empty())
			{
				pair<char, int> current = even.front();
				answer.append(current.second / 2, current.first);
				even.pop();
			}
			string tailParts = answer.substr();
			reverse(tailParts.begin(), tailParts.end());
			answer += tailParts;
			cout << answer << "\n";
		}
	}
	else
	{
		if (odd.size() != 1)
		{
			cout << "I'm Sorry Hansoo" << "\n";
		}
		else
		{
			char oddChar = 'A';
			while (!even.empty())
			{
				pair<char, int> current = even.front();
				if (!odd.empty() && odd.front() < current)
				{
					answer.append(odd.front().second / 2, odd.front().first);
					oddChar = odd.front().first;
					odd.pop();
				}
				else
				{
					answer.append(current.second / 2, current.first);
					even.pop();
				}
			}
			if (!odd.empty())
			{
				answer.append(odd.front().second / 2, odd.front().first);
				oddChar = odd.front().first;
				odd.pop();
			}
			string tailParts = answer.substr();
			reverse(tailParts.begin(), tailParts.end());
			answer += oddChar;
			answer += tailParts;
			cout << answer << "\n";
		}
	}
	return 0;
}