백준 - 1213번 : 팰린드롬 만들기(C++)

풀이 방법 : 그리디

먼저 주어진 문자열이 팰린드롬으로 만들 수 있는지 따진다.

주어진 문자열에 들어있는 각 알파벳들의 수를 카운팅 했을 때 홀수인 알파벳이 1개보다 더 많이 있다면 그 문자열은 팰린드롬으로 만들 수 없다.
이를 따지기 위해서 map을 이용해서 카운팅을 해줬다.

팰린드롬으로 만들 수 있는 문자열일 경우 알파벳 순서대로 빈 문자열에 추가하고 스택에 해당 문자를 집어넣는다. map은 이진 탐색 트리로 구현되어있기 때문에 정렬되어있으니 map의 순서대로 추가하면 자동적으로 사전순으로 앞서는 문자열이 완성 될 것이다.

만약 알파벳중에 홀수개인 것이 들어있다면, 그것이 가운데에 들어가야할 문자다. 마지막에 넣어주자.

가운데 문자까지 삽입이 끝났다면 stack에 쌓인 문자들을 스택이 빌 때까지 문자열에 추가해주면 팰린드롬 문자열이 완성된다.

#include <iostream>
#include <string>
#include <stack>
#include <map>

using namespace std;

int main()
{
	string N;

	cin >> N;

	map<char, int> mapAlpha;

	for (int i = 0; i < N.length(); ++i)
	{
		++mapAlpha[N[i]];
	}

	auto iter = mapAlpha.begin();
	auto iterEnd = mapAlpha.end();

	int Cnt = 0;
	bool Enable = true;

	for (; iter != iterEnd; ++iter)
	{
		if (iter->second % 2 == 1)
			++Cnt;

		if (Cnt > 1)
		{
			Enable = false;
			break;
		}
	}

	if (!Enable)
	{
		cout << "I'm Sorry Hansoo";
		return 0;
	}

	iter = mapAlpha.begin();

	string Answer = "";
	stack<char> sChar;
	char Mid  = ' ';

	for (; iter != iterEnd; ++iter)
	{
		while (iter->second > 1)
		{
			Answer += iter->first;
			sChar.push(iter->first);
			iter->second -= 2;
		}

		if (iter->second == 1)
			Mid = iter->first;
	}

	if(Mid != ' ')
		Answer += Mid;

	while (!sChar.empty())
	{
		char T = sChar.top();
		sChar.pop();
		Answer += T;
	}

	cout << Answer;

}