백준 17609 C++ 회문

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

17609번: 회문

해당 문자열이 회문인지 아닌지, 그리고 한 글자를 뺐을 때 회문인지 판단하는 문제입니다.

 

단순히 한글자 씩 빼서 회문인지 검사하면, string의 최대 길이가 100,000 이하 이므로 최악의 경우 100,000 * 50,000 번의 검사를 해야합니다. (한 번에 2개 문자 검사 가정)

 

그러므로 투 포인터를 응용하여 해당 문자열이 회문인 경우 계속 진행하고, 서로 다른 문자가 나온 경우, check count를 1개 올려줍니다. 기회를 한 번 더 주는 것입니다. 그리고 추가로 진행을 하며 또 다시 회문이 되지 않으면 해당 문자열은 유사 회문이 될 수 없습니다. 

 

코드는 다음과 같습니다.