문제 설명

문제 바로가기
동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.

동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.

동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.

생각해보기

어떠한 팰린드롬 문자열을 $P$라고 하자.
그리고 다른 어떠한 문자열을 $W$라고 하자.
W의 reverse를 $W^{-1}$라고 하자.
$W + P + W^{-1}$ 또한 팰린드롬 문자열이다.

주어진 문자열 $S$를 $W$와 $P$로 나눌 수 있다.
$S = W + P$
그러면 구하는 최종 문자열의 길이 $C$는
$C = Len(S) + Len(W)$ 가 된다.

풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        String S = new BufferedReader(new InputStreamReader(System.in)).readLine();
        int idx = 0;
        while(!isPalindrome(S, idx)){
            idx++;
        }
        System.out.println(idx + S.length());
    }

    private static boolean isPalindrome(String S, int start) {
        int end = S.length()-1;
        while(start < end) {
            if(S.charAt(start) != S.charAt(end))
                return false;
            start++;
            end--;
        }
        return true;
    }
}

while loop를 돌며 idx가 증가한다.
while을 탈출한 후 idx는 $Len(W)$를 의미한다.