[BOJ] 백준 17609번: 회문

문제

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다. 

 

풀이

처음 이 문제를 접하면 제일 처음 드는 생각은 각 문자열마다 한문자씩 제외하면서 회문인지 체크하면 되지 않나? 라는 의문입니다. 하지만 시간제한이 1초이기에 각 문자열 길이마다 체크하게되면 무조건 시간초과가 나게 됩니다.

따라서 문자열을 투 포인터를 이용해 만약 L자리와 R자리의 문자가 다를 경우 재귀를 통해 다른 개수를 받아와 비교하는 형식이 제일 올바른 풀이방법 같습니다.

 

코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int T;
    static String str;


    static void input() throws IOException{
        str = br.readLine();
    }

    static int process(int L, int R, int cnt){
        if(cnt == 2) return 2;

        while(L < R){
            if(str.charAt(L) != str.charAt(R)){
                int leftPalind = process(L+1, R, cnt+1);
                int rightPalind = process(L, R-1, cnt+1);
                return Math.min(leftPalind, rightPalind);
            }
            L+=1; R-=1;
        }
        return cnt;
    }

    public static void main(String[] args) throws IOException{
        int T = Integer.parseInt(br.readLine());
        while(T-->0){
            input();
            sb.append(process(0, str.length()-1, 0)).append('\n');
        }
        System.out.print(sb);
    }
}

 

 

<출처>

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