백준 1254번 팰린드롬 만들기 C++

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

 

최소한의 알파벳으로 팰린드롬을 만드는 문제이다. (앞에서부터 읽는 것과 뒤에서부터 읽는 것이 같은 문자열)

 

주어진 문자열을 탐색하는데, 시작 지점을 1씩 늘려가면서 만약 팰린드롬이라면 문자열의 길이에 시작 지점을 더해서 문제를 해결하였다.

 

그림으로 그려보면

그림을 좀 못 그린 것 같긴 한데 설명을 해보자면, 처음 a와 e는 같지 않으므로 팰린드롬이 될 가능성이 없다. 그래서 시작 지점을 1 늘려준다.  그때 b와 e도 같지 않으므로 또 늘려준다. 이렇게 진행하다가 3번 인덱스 e에 도착했을 때 마지막 e와 같으므로 팰린드롬일 가능성이 있기 때문에 계속 검사를 해준다. 검사를 마쳤을 때 팰린드롬이 맞았기 때문에 문자열의 길이 8과 검사를 시작했던 인덱스 3을 더하면 11이 된다. ( abcefgfe + cba ) -> cba 부분을 더해준 것.

 

이런 방식을 이용해서 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

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

	string str;
	cin >> str;
	int cnt = 0;
	int ans;
	while (true) {
		int start = cnt;
		int end = str.length() - 1;
		while (start <= end) {
			if (str[start] != str[end]) break;
			start++;
			end--;
		}
		if (start > end) {
			ans = str.length() + cnt;
			break;
		}
		cnt++;
	}
	cout << ans;
};