[BOJ-17609] 회문 (JAVA)

백준 17609 회문

 

17609번: 회문

 

 

문제 설명

 

 - 팰린드롬(Palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다.

 

 - 회문이 아닌 문자열에서 한 문자를 제거하여 회문이 만들어 지는 문자열을 유사 회문(pseudo palindrome)이라고 한다.

   예를 들어, summuus의 5번째 혹은 6번째 문자 u를 제거하여 만든 문자열 summus은 유사 회문이다.

 

 - 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 유사회문인지, 둘 다 아닌지 판단하라.

 

 - 회문이면 0, 유사 회문이면 1, 둘 다 아니면 2를 순서대로 한 줄에 하나씩 출력하라.

 

 

 

 

---

 

입력 값

 

 - 첫 줄에는 주어지는 문자열의 개수 T ( 1 <= T <= 30 ) 가 주어진다.

 

 - 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다.

 

 - 주어지는 문자열의 길이는 3 이상, 100,000 이하이고, 영문 알파벳 소문자로 이루어져 있다.

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 회문인지, 유사 회문인지, 아무것도 아닌지 판단하는 문제이다.

 

 - 기본적으로 회문인지 판단하는 방법은 양 끝점부터 같은 문자가 나오는지 판단하면 된다.

   즉, 문자의 길이가 N이라 하면, N/2 만으로 회문인지 판단할 수 있다.

 

 - 이 문제에서 가장 큰 문제는 유사 회문인지 판단하는 방법이다.

 

 - 유사 회문인지 판단하는 가장 간단한 방법은, 한 문자를 제거하여 회문이 되는지 판단하는 것이다.

 

 - 이 경우, 문자의 길이가 N일때 한 문자를 선택하는 경우 방법 N, 회문인지 판단하는 N/2의 경우가 존재하기 때문에

   O($N^2$)의 시간복잡도가 걸린다. 

 

 - 문자열의 길이는 최대 10만이기 때문에  O($N^2$)의 시간복잡도는 불가능하다.

 

 - 그렇답면 어떻게 해야 할까?

 

 - 유사 회문의 특성을 살펴보면 간단하게 해결할 수 있다.

 

 - 유사 회문이란 기존 문자열에서 한 문자를 제거한 후 회문이 되는 문자를 말한다.

 

 - 즉, 제거해야 하는 문자가 나오기 전까지는 회문의 특성을 가지고 있고,

   제거해야 하는 문자는 회문의 특성을 가지고 있지 않다는 것이다.

 

 - 정리해 보자면,

   1. 양 끝점에서 중간으로 이동하며 문자가 같은지 비교한다.

   2. 중간까지 이동이 되었다면 회문이라고 판단한다.

   3. 중간까지 이동 전 다른 문자가 존재하게 된다면, 해당 문자 2개를 각각 지워서 회문인지 판단한다.

   4. 문자 제거 후 회문이라면 유사회문이라고 판단한다.

   5. 문자 제거 후 회문이라고 판단할 수 없다면, 둘 다 아니라고 판단한다.

 

 

 

 

 

 

---

 

 

소스 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

// https://www.acmicpc.net/problem/17609
// 회문
public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(bf.readLine());

        StringBuilder sb = new StringBuilder();

        for(int t=0;t<T;t++){
            String s = bf.readLine();
            sb.append(checkPalindrome(s,0,0,s.length()-1));
            sb.append("\n");
        }
        System.out.println(sb);
    }

    // start 와 last 계속 비교하여 회문인지 판단
    // result 0 : 회문 / result 1 : 유사회문 / result 2 : 아무것도 아님
    public static int checkPalindrome(String s,int result, int start,int last){

        if(result==2){
            return 2;
        }

        while(start<=last){

            if(s.charAt(start) == s.charAt(last)){
                start++;
                last--;
            }
            else{
                // 현재는 회문이 아니다 -> 하나씩 제거하여 비교해서 회문인지 판별
                // 더 작은 값으로 갱신
                result = Integer.min(checkPalindrome(s,result+1,start+1,last),checkPalindrome(s,result+1,start,last-1));
                break;
            }
        }
        
        return result;
    }
}