[백준 / BOJ] C++ 17609 회문

17609번: 회문

 

문제

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

17609번: 회문

 

 

풀이

문자열을 입력받아 이 문자열이 회문인지, 유사 회문인지, 둘 다 아닌지를 판단하여 각 0, 1, 2를 출력하는 문제다. 여기서 유사 회문이란 문자열에서 한 글자를 제거하여 회문이 되는 문자열을 말한다.

 

투 포인터(two pointer)를 사용해 풀었다. 문자열을 s라 하면, left는 0번 index부터 차례로 증가, right는 문자열의 마지막 문자 index부터 차례로 감소하며 left < right 조건을 만족하는 동안 문자를 비교했다. 회문이라면 s[left] == s[right]를 만족해야 하기 때문이다. s[left] == s[right]이면 left는 1 증가, right는 1 감소시키며 확인했다.

 

예를 들어 "abba"라는 문자열에서 left = 0, right = 3이다. s[left] == s[right]는 모두 'a'이므로 left는 1 증가, right는 1 감소할 것이다. left = 1이 되고 right = 2가 된다. s[left] = s[right]는 모두 'b'가 되고 이 문자열은 회문이 된다.

 

다음은 회문이 아닌 경우가 있다. 이는 유사 회문인 경우와 유사 회문도 아닌 경우다. 유사 회문은 하나를 삭제해서 회문이 되는 경우다. s[left]와 s[right]를 비교하다가 어느 순간 s[left]와 s[right]가 다른 순간이 하나를 삭제하는 경우다. 문자열이 같을 땐 삭제할 필요가 없기 때문이다. 여기서 하나 더 확인해야 할 것이 있다. 바로 삭제한 문자가 0 개인 지다. 이미 1개를 삭제했는데 또 삭제해야 할 상황이 오면 이는 유사 회문도 아니기 때문이다.

 

만약 삭제가 가능한 경우에도 s[left]를 삭제하는 경우와 s[right]를 삭제하는 경우가 있을 것이다. 어느 하나를 삭제했을 때 나머지가 회문이라면 이 문자열 s는 유사 회문인 것이고 회문이 아니라면 유사 회문도 아니라는 것을 의미한다.

 

만약 s[left]와 s[right]가 다르다면, s[left]를 제거한 나머지 문자열과 s[right]를 제거한 나머지 문자열 중 하나가 회문이면 문자열 s는 유사 회문이다. 문자열 s에서 문자를 제거할 수 있는 횟수는 1회뿐이므로 err 변수를 만들어 0부터 시작하게 만들었다. 그리고 제거한 나머지 문자열을 확인하려면 같은 과정을 반복해야 하므로 함수로 만들어 다시 호출하도록 만들었다.

 

 

 

코드

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

int isPal(string s, int err) {
  int left = 0, right = s.size() - 1;
  while (left < right) {
    if (s[left] != s[right]) { // 문자가 다른 경우
      if (err == 0) { // 문자를 삭제하지 않은 경우
        int len = right - left;
        // 남은 문자열이 회문인지 확인
        if (isPal(s.substr(left, len), err + 1) == 0 || isPal(s.substr(left + 1, len), err + 1) == 0) // 회문인 경우
          return 1;
        else // 회문이 아닌 경우
          return 2;
      } else { // 문자를 이미 삭제한 경우
        return 2;
      }
    }
    left++;
    right--;
  }
  // 문자열이 회문인 경우
  return 0;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    cout << isPal(s, 0) << '\n';
  }
  return 0;
}