백준 JAVA 17609번 회문

문제 링크: https://www.acmicpc.net/problem/17609

17609번: 회문

 

 

문제를 접할 때 회문이 아닐 경우에 for문을 중첩해서 한 글자씩 빼낸 후 확인을 했을 경우 시간초과가 나왔다. (해당 코드 첨부)

import java.math.BigInteger;
import java.util.*;
import java.io.*;



public class Main {

    static int t;
    static boolean check;
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t= Integer.parseInt(br.readLine());
        for(int i=0; i<t; i++){
            String s = br.readLine();

            if(check(s)){
                System.out.println(0);
                continue;
            }
            else{
                for(int j=0; j<s.length(); j++){
                    if(ReCheck(s,j)){
                        check=true;
                        break;
                    }
                }
            }
            if(check){
                System.out.println(1);
            }
            else{
                System.out.println(2);
            }
            check=false;
        }
    }

    public static boolean check(String str){
        int left = 0;
        int right = str.length()-1;

        while(left<=right){
            if(str.charAt(left)!=str.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static boolean ReCheck(String str, int index){
        String string = makeNewString(str, index);
        return check(string);
    }
    public static String makeNewString(String str, int index){
        String str1 = str.substring(0, index);
        String str2 = str.substring(index + 1);
        return str1.concat(str2);
    }
}

 

그래서 양쪽 끝을 하나씩 비교하고 틀렸을 경우 양쪽을 번갈아 빼고 비교를 하여 for문을 하나 줄였다.

 

import java.math.BigInteger;
import java.util.*;
import java.io.*;



public class Main {

    static int t;
    static String s;
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t= Integer.parseInt(br.readLine());
        for(int i=0; i<t; i++){
            s = br.readLine();

            if(check(0, s.length()-1)){
                System.out.println(0);
            }
            else{
                if(ReCheck(0,s.length()-1)){
                    System.out.println(1);
                }
                else{
                    System.out.println(2);
                }
            }
        }
    }

    public static boolean check(int left, int right){

        while(left<=right){
            if(s.charAt(left)!=s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static boolean ReCheck(int left, int right){

        while(left<=right){
            if(s.charAt(left)!=s.charAt(right)){
               boolean a = check(left+1,right);
               boolean b = check(left, right-1);
               if(!a && !b){
                   return false;
               }
               else{
                   return true;
               }
            }
            left++;
            right--;
        }
        return true;
    }

}

 

 

 

-- 다른 알고리즘보다 문자열이 가장 어려운 거 같다.. --