[JAVA] 백준 17609 회문_탐색

 

문제 : 

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

 

 

접근 : 

 

 - 좌측 끝과 우측 끝에 포인터를 두고 양쪽에서 1씩 감소시키면서 일치하는지 판단한다.

 

  - 만약 다르다면 현재 좌측+1, 우측 포인터 위치에서 다시 한번 검사를 실시한다.

 

  - 또한, 현재 좌측, 우측-1 포인터 위치에 대해서도 검사를 실시하고 둘 중 작은 값을 결과로 출력한다.

 

 

코드 구현 :

 

import java.io.*;

public class Main {
    private static int checkPal(String str, int s, int e, int rm_cnt){
        if (rm_cnt >= 2) return 2;

        while (s < e) {
            if (str.charAt(s) == str.charAt(e)) {
                s++;
                e--;
                continue;
            }
            return Math.min(checkPal(str,s+1, e, rm_cnt+1), checkPal(str, s, e-1, rm_cnt+1));
        }
        return rm_cnt;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        String input;

        for(int i = 0 ; i < t; i++){
            input = br.readLine();
            sb.append(checkPal(input,0,input.length()-1,0)).append("\n");
        }
        System.out.print(sb);
        br.close();
    }
}