(1254) 팰린드롬 만들기

문제

문제
동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다.

출력
첫째 줄에 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력한다.

---

문제풀이

문제안에 문자열의 보다보면 답이 있는 문제 였다. 입력 예제로 주어지는 문자열을 보면 팰린드롬을 구성할 수 없는 부분까지는 처음 문자와 끝문자가 맞지 않다가 구성될 수 있는 순간에는 비교 문자들이 맞게 된다는 규칙이 있다.

 

아래 문자열 `abab`가 있다. 여기서 현재 index 0 과 3의 값은 다르다. 그러면 0을 지나서 1과 3을 비교한다면 같은 모양을 가지는 팰린드롬의 조건이 될 수 있다. 

이러한 규칙을 이용하여서 원래 길이 + 몇 번을 이동을 하였는가에 대한 값을 정리해서 값으로 반환 하면 쉽게 길이를 알 수 있다. 

---

나의 답안

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        String s = scan.nextLine();
        int len = s.length();
        int answer = len;

        for (int i = 0; i < len; i++) {
            if (!solution(s.substring(i))){
                answer++;
            } else {
                break;
            }
        }

        System.out.println(answer);;

    }

    static boolean solution(String s) {
        int left = 0;
        int right = s.length() -1;

        while (left <= right) {
            if (s.charAt(left) == s.charAt(right)){
                left++;
                right--;
            } else {
                return false;
            }
        }

        return true;
    }
}