회문

📍 문제 설명

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

17609번: 회문

 

💡 접근

회문이 아닌 경우에 왼쪽 문자를 무시하거나 오른쪽 문자를 무시하여 회문을 확인하는 절차가 필요하다

 

1. StringBuilder의 deleteChatAt 사용하는 방법

2. 팰린드롬 아닐경우 해당 양 옆의 문자를 제거하여 팰린드롬 재확인하는 방법

 

StringBuilder의 경우 shift 과정 때문에 메모리를 약 2배 더 잡아먹었다.

 

👩‍💻 코드

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] visited;
    static int n, m, k, t;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main main = new Main();

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        for (int tc = 0; tc < n; tc++) {
            StringBuilder sb = new StringBuilder(br.readLine());

            if(sb.toString().equals(sb.reverse().toString())) {
                System.out.println(0);
                continue;
            }
            for (int i = 0; i < sb.length()/2; i++) {
                if(sb.charAt(i) != sb.charAt(sb.length()-i-1)) {
                    //다른 부분으로 문자열 만들어서 다시 체크
                    StringBuilder sb1 = new StringBuilder(sb);
                    StringBuilder sb2 = new StringBuilder(sb);
                    sb1.deleteCharAt(i);
                    sb2.deleteCharAt(sb.length()-i-1);
                    if(sb1.toString().equals(sb1.reverse().toString())
                            || sb2.toString().equals(sb2.reverse().toString())) {
                        System.out.println(1);
                    } else {
                        System.out.println(2);
                    }
                    break;
                }
            }
        }
    }

}

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] visited;
    static int n, m, k, t;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main main = new Main();

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        for(int tc = 0; tc < n; tc++) {
            String str = br.readLine();

            //회문일 경우
            if(palindromeCheck(0, str.length()-1, str)) System.out.println(0);
            //회문아닐 경우(유사회문인지, 유사회문도 아닌지 판단)
            else
                if(palindromeReCheck(0, str.length()-1, str)) System.out.println(1);
                else System.out.println(2);
        }


    }

    private static boolean palindromeReCheck(int lt, int rt, String str) {
        while(lt < rt) {
            if(str.charAt(lt) != str.charAt(rt)) {
                //lt 이전 것과 rt 이후 것들은 판단 완료한 상태이니 그 이후 문자열들 check
                //lt 무시하고 그 이후 확인
                boolean a = palindromeCheck(lt + 1, rt, str);
                //rt 무시하고 그 이후 확인
                boolean b = palindromeCheck(lt, rt - 1, str);
                //팰린드롬되는 거 하나도 없으면 아무것도 아니다.
                if(!a && !b) return false;
                else return true;
            }
            lt++; rt--;
        }
        return true;
    }

    private static boolean palindromeCheck(int lt, int rt, String str) {
        while(lt < rt) {
            if(str.charAt(lt) != str.charAt(rt)) return false;
            lt++; rt--;
        }
        return true;
    }
}