[java][백준] 17609 - 회문

문제

풀이

문제 해석

1. 회문은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. ex) 'abba', 'qwerewq' 등

2. 완전한 회문은 아니지만 글자 중 하나를 지워서 회문이 된다면 유사회문이라고 부른다. ex) 'summuus' 'xabba' 등

3. 첫째 줄에 테스트 케이스 T를 입력으로 밑으로 T개의 줄에 문자열이 입력으로 주어진다.

4. 각 테스트 케이스가 회문이면 0, 유사회문이면 1, 둘 다 아니면 2를 출력한다.

 

풀이

1. 처음과 끝을 비교하여 같으면 한칸씩 전진, 후진한다.

2. 만약 다른 글자가 나오면 각각을 지운 후 회문이 되는지 확인한다.

3. 회문이 된다면 유사회문이고 안된다면 보통 문자열이다.

소스코드

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

/**
 * 회문
 * 골드 5
 */
public class No17609 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder answer = new StringBuilder();
        while(t-->0){
            String str = br.readLine();
            answer.append(isPalindrome(str)).append("\n");
        }
        System.out.println(answer);
    }

    private static int isPalindrome(String str) {
        StringBuilder sb = new StringBuilder(str);

        int lt = 0;
        int rt = str.length()-1;
        while(lt < rt){
            if(sb.charAt(lt) == sb.charAt(rt)){
                rt--;
                lt++;
            }else{
                StringBuilder delLeft = new StringBuilder(sb).deleteCharAt(lt);
                StringBuilder delRight = new StringBuilder(sb).deleteCharAt(rt);
                if(delLeft.toString().contentEquals(delLeft.reverse())
                    || delRight.toString().contentEquals(delRight.reverse())){
                    return 1;
                }
                return 2;
            }
        }

        return 0;
    }
}

 

마무리

1. StringBuilder의 강력함을 깨달았다.

2. StringBuilder의 reverse() 메서드는 O(n)의 시간 복잡도를 가진다.