[백준 17609번-C++] 회문

http://acmicpc.net/problem/17609

{코드}

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

string s;

int isPalindrome(int left, int right, bool testPseudo) {
  while (left < right) {
    if (s[left] != s[right]) {
      if (testPseudo) {
        if (isPalindrome(left+1, right, false) == 0 || isPalindrome(left, right-1, false) == 0) return 1;
      }
      return 2;
    }
    left++; right--;
  }
  return 0;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  while(n--) {
    cin >> s;
    cout << isPalindrome(0, s.length() - 1, true) << '\n';
  }
}

{설명}

우선 회문을 판별하기 위해 투 포인터 기법을 사용합니다.

투 포인터는 간단하게 설명하자면 처음과 끝에서 서서히 중간으로 인덱스를 이동하며 두 값을 비교한다고 보시면 됩니다.

그렇게 회문을 판별하다 아니라고 판단되면 유사회문인지 아닌지를 판별해야 합니다.

여기서 요점은 지워야 하는 문자가 앞에 있을 수도, 뒤에 있을 수도 있으며 둘 다 판별을 해줘야 한다는 것입니다.

그렇기에 인덱스를 사용하여 왼쪽을 한 칸 오른쪽으로 이동시키거나 오른쪽을 한 칸 왼쪽으로 이동시켜 다시 회문 판별을 합니다.

둘 중 하나만이라도 참이면 되기 때문에 || (또는/or) 를 사용하며 solution 함수에서 최종적으로 문자열을 판별합니다.

*main의 첫 두 줄에 대한 설명은 이 글을 참고해주시기 바랍니다. 간단하게는 입/출력 속도를 빠르게 하는 역할을 합니다.