[BOJ/C++] 팰린드롬 만들기 - 1254번 / CPP풀이

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

1254번: 팰린드롬 만들기

 

문자열 S를 받아 해당 문자열에서 N개의 문자를 추가하여 팰린드롬을 만드는 문제이다.

단, S의 길이는 최소로 해야한다.

 

우선 임의의 문자열에서 팰린드롬을 만들 수 있는 방법은 무엇이 있을까?

abab : a만 추가하면 된다.

abbb : a만 추가하면 된다.

aabb : a를 2개 추가해야한다.

abba : 그 자체로 팰린드롬

 

팰린드롬을 만드는 규칙이 있을까?

길이를 반으로 나누어 문자를 추가하고 합쳐보고 이런 저런 생각을 해봤지만 잘 생각이 나지 않았다...

 

그렇다면 문자열 S를 무조건 팰린드롬으로 만드는 방법은 무엇이 있을까?

바로 S를 거꾸로 한 문자열을 S의 뒤에 붙여주면 된다.

ex) qwerty + ytrewq = qwertytrewq

 

문자열 S를 무조건 팰린드롬으로 만드는 방법은 찾았는데, 만약 그것보다 더 짧은 팰린드롬이 존재한다면?

S = ab
무적 팰린드롬 방법 : ab + ba = 4

최소 팰린드롬 방법 : aba = 3

 

무적 팰린드롬 방식은 최소를 보장해주지 못한다.

그렇다면 어떻게 최소 팰린드롬을 구할 수 있을까?

 

무적 팰린드롬 방식으로 알 수 있는 것은 무적 팰린드롬 방식은 최소 팰린드롬을 무조건 포함한다는 것이다.

(최소 팰린드롬은 원본 문자들로만 이루어지기 때문에 원본 문자 + α인 무적 팰린드롬은 무조건 최소 팰린드롬을 포함할 수 밖에 없다.)

 

 

- 결론 -

 

1. 원본 문자열을 거꾸로 한 것을 원본 문자열에 붙여주고 (abb -> abb bba)  

2. 팰린드롬인지 확인한다.

3. 팰린드롬이 맞다면 최소값으로 갱신시켜준다.

4. 추가한 문자열의 맨 앞 문자를 삭제한다 (abb -> abb [ ]ba)

5. 원본 문자열의 길이가 될 때까지 2~4를 반복한다. (abb -> abb [ ][ ]a)

 

#include <bits/stdc++.h>
using namespace std;

bool IsPalin(string &s) {
	bool ans = true;
	for (int i = 0, j = s.length()-1; i < s.length(); i++, j--) {
		if (s[i] != s[j]) {
			ans = false;
		}
	}
	return ans;
}

string StringDouble(string& s) {
	string retStr = s;

	for (int i = s.length() - 1; i > -1; i--) {
		retStr += s[i];
	}

	return retStr;
}

int main() {
	string s; cin >> s;
	int ans = s.length();

	// 맨 처음부터 회문일 경우 기존 문자열의 크기를 출력
	if (IsPalin(s)){
		cout << ans;
	}
	// 팰린드롬을 만들어야 할 경우
	else {
		// 2배를 해주고, 추가된 문자열의 맨 앞부터 빼주며 검사함
		// 만약, 원래 문자열의 크기까지 회문이 나오지 않을 경우 X2 한 것이 정답이 됨.
		string newStr = StringDouble(s);
		
		int ptr = s.length();
		ans = s.length() * 2;
		while (newStr.length() > s.length()) {
			newStr.erase(ptr, 1);
			if (IsPalin(newStr)) {
				ans = newStr.length();
			}
		}

		cout << ans;
	}
}

 

정해인지는 모르겠다.