백준 [자바 java] 17609 : 회문

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

17609번: 회문

 

처음에는 자료구조 시간에 회문 문제 스택으로 풀라고 했던 것 기억나서 그렇게 했는데 시간초과가 났다.

그래서 문제를 자세히 살펴보니 투포인터로 하는게 훨씬 효율적이었다.

여기서 두 포인터의 char값이 다를 때 값을 옮겨주는 과정에서 옮긴 후 모든 것들은 회문이어야 한다는 조건을 빼먹어서 틀렸습니다가 나왔다.

 

주의할 점 

구현 까다로우면 더 쉬운 방법 있나 한번 더 생각하기

반례 더 있나 깊게 생각하기

 

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


public class Main {

    static char[] arr;

    static int check(int a, int b){
        int fir = a;
        int sec = b;

        while(fir<sec){
            if(arr[fir] != arr[sec]){
                return 0;
            }
            fir++;
            sec--;
        }
        return 1;
    }


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

        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            String k = br.readLine();

            arr = k.toCharArray();

            int fir = 0;
            int sec = arr.length-1;

            int ans = 0;

            while(fir < sec){

                if(arr[fir] != arr[sec]){
                    if(ans != 0) {
                        ans = 2;
                        break;
                    }
                    if(arr[fir+1] == arr[sec] && check(fir+1, sec) == 1){
                        fir++;
                        ans++;
                    }
                    else if(arr[fir] == arr[sec-1] && check(fir, sec-1) == 1){
                        sec--;
                        ans++;
                    }
                    else{
                        ans =2;
                        break;
                    }
                }
                fir++;
                sec--;
            }

            System.out.println(ans);


        }
    }
}