[백준 1213] 팰린드롬 만들기

문제 풀이

 

문자열이 주어졌을 때 이를 적절하게 섞어서 팰린드롬을 만들 수 있다면, 만들 수 있는 경우에서 사전 순으로 가장 앞서는 문자열을 출력하는 문제입니다.

 

예제 입력을 잘보면 규칙을 찾을 수 있습니다.

주어진 문자열의 길이가 짝수이면? 팰린드롬을 만들려면 해당 알파벳이 모두 짝수개여야 합니다.

만일 홀수개가 존재한다면 그건 어떤 방법을 사용해도 절대 만들 수 없습니다.

 

주어진 문자열의 길이가 홀수이면? 팰린드롬을 만들 때 가운데 홀수 알파벳을 제외하고 나머지는 모두 짝수개의 알파벳을 가지고 있어야 만들 수 있습니다. 주의할 점은 홀수 알파벳이 두 개 이상 존재한다면 역시 만들 수 없습니다.

A B C D 모두 각각 홀수 1개씩 가지지만 절대 팰린드롬을 만들 수 없는 것처럼 말이죠.

 

위에서 걸리는 조건이 있다면 절대 만들 수 없을 것이고, 위의 조건에 위배되지 않는다면?

우리는 가장 사전순으로 빠른 팰린드롬을 만들어야 합니다.

 

문자열의 길이가 짝수라면 가장 알파벳 사전 순이 뒤에 있는 것부터 안쪽부터 채워나가면 됩니다.

AABB (A가 2개, B가 2개) 이므로
안쪽부터 채워나가면
BB
ABBA

 

만약에 문자열의 길이가 홀수라면? 홀수 알파벳을 먼저 가운데에 채워 넣고, 위와 마찬가지로 사전 순으로 느린 것부터 안쪽을 채워나가면 됩니다.

ABACABA (A가 4개, B가 2개, C가 1개) 이므로
안쪽부터 채워나가면
C
BCB
ABCBA
AABCBAA

안쪽부터 어떻게 채울 수 있을까요? 저는 deque 자료구조를 이용해서 앞이랑 뒤에 알파벳을 넣는 방식으로 구현했습니다.

 

소스 코드

#include <iostream>
#include <string>
#include <deque>
using namespace std;

int alpha[26];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++)
	{
		alpha[s[i] - 'A']++;
	}

	bool ok = true;
	deque<char> dq;
	if (s.size() % 2 == 0)
	{
		for (int i = 0; i < 26; i++)
		{
			if (alpha[i] > 0 && alpha[i] % 2 != 0)
			{
				ok = false;
				break;
			}
		}

		for (int i = 25; i >= 0; i--)
		{
			int sz = alpha[i] / 2;
			for (int j = 0; j < sz; j++)
			{
				dq.push_back(i + 'A');
				dq.push_front(i + 'A');
			}
		}
	}
	else
	{
		int odd = 0, idx = -1;
		for (int i = 0; i < 26; i++)
		{
			if (alpha[i] > 0 && alpha[i] % 2 != 0)
			{
				odd++;
				idx = i;
			}
		}

		// 주의할 점은 홀수 개는 딱 1개만 존재해야 만들 수 있습니다.
		if (odd > 1 || odd <= 0)
		{
			ok = false;
		}

		dq.push_back(idx + 'A');
		alpha[idx]--;

		for (int i = 25; i >= 0; i--)
		{
			int sz = alpha[i] / 2;
			for (int j = 0; j < sz; j++)
			{
				dq.push_back(i + 'A');
				dq.push_front(i + 'A');
			}
		}
	}

	if (ok == false)
		cout << "I'm Sorry Hansoo\n";
	else
	{
		for (auto c : dq)
		{
			cout << c;
		}
		cout << endl;
	}
	return 0;
}