백준 17609 회문 자바(java)

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

17609번: 회문

 

풀이 방법

투 포인터 문제이다.

• 왼쪽 포인터 변수 left = 0, 오른쪽 포인터 변수 right = 문자열길이 - 1 을 선언한다.
• 먼저, left, right 를 넘겨 회문인지 확인하는 함수를 호출한다. 함수 동작은 아래와 같다.
  • left 는 하나씩 증가시키면서, right는 하나씩 감소시키면서 현재 문자가 같은지 확인한다.
  • 문자가 다른 경우엔 회문이 될 수 없으므로 false를 바로 리턴한다.
  • 같으면 다음 문자 확인으로 넘어가고 마지막까지 같은 경우 true를 리턴한다.
  • true가 리턴되면 회문이므로 0을 출력한다.
• 위에서 회문이 아니면 유사 회문인지 체크한다.
  • left, right를 증가, 감소시키면서 문자가 같은지 확인한다.
  • 문자가 다르면 왼쪽 문자를 삭제하는 경우 left+1, right를 회문 체크 함수로 넘겨 회문인지 확인한다.
  • 오른쪽 문자를 삭제하는 경우는 left, right-1를 회문 체크 함수로 넘겨 회문인지 확인한다.
  • 왼쪽 문자나 오른쪽 문자를 삭제했을 때 둘 중 하나가 true를 리턴하면 유사 회문이므로 1을 출력한다.
  • 둘 다 false 라면 일반 문자열이므로 2를 출력한다. 

 

코드

import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++) {
            String str = br.readLine();

            int result = 2;
            if(isPalindrome(str, 0, str.length()-1)) { // 회문이면
                result = 0;

            } else {
                // 유사회문인지 체크
                int left = 0;
                int right = str.length()-1;
                while(left < right) {
                    // 현재 문자가 서로 다르면 왼쪽, 오른쪽 하나씩 지워보고 회문인지 체크
                    if(str.charAt(left) != str.charAt(right)) {
                        boolean removeLeft = isPalindrome(str, left+1, right);
                        boolean removeRight = isPalindrome(str, left, right-1);
                        if(removeLeft || removeRight) {
                            result = 1;
                        }
                        break;
                    }
                    left++;
                    right--;
                }
            }
            System.out.println(result);
        }
    }

    public static boolean isPalindrome(String str, int left, int right) {
        while(left < right) {
            if(str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}