[백준] 회문

문제

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

알고리즘

문자열
정렬
투포인터

풀이

일단 투포인터 알고리즘으로 회문인지 아닌지 판별할 수는 있다.
하지만 유사 회문인 경우는 한 문자만 빼서 회문이면 유사 회문이라고 한다.
유사 회문인지 알기 위해서는 일단 회문인지 판별을 하다가 문자가 다른 경우라면 왼쪽 문자를 하나 건너뛰거나 오른쪽 문자를 하나 건너 뛰어서 회문인지 다시 판별한다.
체크할 변수를 처음에는 0으로 설정하고 회문이면 0을 리턴한다.
회문이 아니면 left, right 변수를 하나씩 스킵하고 재귀를 한번 돌려준다.
재귀를 돌려서 0이 나오면 유사 회문이라는 것이다. 만약 스킵을 해서 돌렸는데도 0이 안나오면 유사 회문도 아니라는 말이므로 2를 리턴해준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {

    public void solution(String[] s) {

        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < s.length; i++) {
            System.out.println(checkPalindrome(0, s[i].length() - 1, 0, s[i]));
        }
    }

    // 회문 체크 함수
    private int checkPalindrome(int left, int right, int result, String s) {

        // 재귀를 돌릴 때 result 변수를 +1 해주는데 만약 또 left, right 자릿수가 안맞으면 2가 넘어올 것이다.
        // result가 2가 되면 유사 회문도 안되기 때문에 그대로 2를 리턴해준다.
        if (result == 2) {
            return 2;
        }

        while (left < right) {

            // 회문이라면 다 돌고 0이 리턴될 것이다.
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {

                // 만약 회문이 아니면 left, right를 하나씩 스킵하고 그대로 재귀를 돌려준다.
                // 하나씩 스킵한 재귀 두개를 비교해서 작은 걸 result로 리턴해준다.
                // 만약 유사회문이라면 1이 리턴될 것이다.
                result = Math.min(checkPalindrome(left + 1, right, result + 1, s),
                    checkPalindrome(left, right - 1, result + 1, s));
                break;
            }
        }

        return result;
    }

    public static void main(String[] args) throws IOException {

        Main solution = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = br.readLine();
        }

        solution.solution(s);

    }
}