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

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

문제

---

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.

동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.

동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다.

 

출력

---

첫째 줄에 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력한다.

 

문제 풀이

---

문자열 문제.

팰린드롬은 앞에서부터 읽나 뒤에서부터 읽나 같게 읽히는 문자열이므로 문자열의 가운데를 기준으로 같은 거리에 위치한 두 문자는 같아야 한다. 즉, 앞에서 첫번째 문자와 뒤에서 첫번째 문자와 같아야 하고, 앞에서 두번째 문자와 뒤에서 두번째 문자가 같아야 하는 식이다.

입력 문자열을 거꾸로 만들어 입력 문자열 뒤에 붙이면 팰린드롬이 된다. 이와 같은 방식으로 앞에서부터 길이 i의 문자열을 거꾸로 뒤집은 형태를 입력 문자열에 뒤에 붙여 팰린드롬이 만들어지는지 확인할 수 있다.

위의 예시를 적용해 길이 0부터 길이 n(입력받은 문자열의 길이)까지 문자열을 붙여보며 팰린드롬인지 아닌지 확인한다. 입력 문자열 자체가 팰린드롬일 수 있으므로 길이 0부터 문자열을 확인해주어야 한다.

 

아래는 코드.

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

bool isPelindrome(string str)
{
	bool isPelindrome = true;
	for (int i = 0; i < str.length() / 2; i++)
	{
		if (str.at(i) != str.at(str.length()- 1 - i))
		{
			isPelindrome = false;
			break;
		}
	}
	return isPelindrome;
}

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

	string str;
	string newStr;
	cin >> str;
	newStr = str;
	for (int i = 0; i <= str.length(); i++)
	{
		newStr = str;
		string tail = str.substr(0, i);
		reverse(tail.begin(), tail.end());
		newStr += tail;
		if (isPelindrome(newStr) == true)
		{
			cout << newStr.length() << "\n";
			break;
		}
	}
	return 0;
}