c++ 백준_1254_"팰린드롬 만들기"

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

1254번: 팰린드롬 만들기

 

​

문제 입력 값이 최대 50이라

브루트 포스하게 찾았다.

​

처음 착각했던 것은 문자열 중간에도 삽입 가능한 줄 알았다.

​

문자열 뒤에 추가해야 하므로

하나씩 검사하면서 단순하게 뒤에 추가하는 방법으로 해결했다.

​

​

​

*

입력 값이 작아서 이렇게 단순하게 해결했지만 크다면 문제가 생긴다.

팰린드롬 문제를 해결하는 알고리즘으로

Manacher 알고리즘이 있었다.

​

이걸 공부해야겠다.

 

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

int main(void) {

	string str;
	cin >> str;

	int add = 0;
	int pos = str.size();

	while (1) {
		int i = 0;
		int j = str.size() - 1;

		bool check = true;

		while (i <= j) {
			if (str[i] != str[j]) {
				check = false;
				break;
			}
			i++;
			j--;
		}
		if (check)
			break;
		str.insert(str.begin() + pos, str[add++]);
	}

	cout <<str.size();
}