[JAVA 알고리즘] 회문

John and Brus are studying string theory at the university. Brus likes palindromes very much.
A palindrome is a word that reads the same forward and backward.
John would like to surprise Brus by taking a String s, and appending 0 or more characters to the end of s to obtain a palindrome.
He wants that palindrome to be as short as possible.
Return the shortest possible length of a palindrome that John can generate.

 

다음은 한글 번역입니다.

존과 브루스는 문자열 이론을 공부하고 있다. 브루스는 회문을 아주 좋아한다.

회문은 앞에부터 읽으나, 뒤에부터 읽으나 같은 단어를 말한다.

존은 문자열  s 에 0개 이상의 문자를 더해 회문을 만들어 부르스를 놀래키고 싶어한다.

그는 최대한 짧은 회문을 만들려고 한다.

존이 생성할 수 있는 가장 짧은 회문의 길이를 리턴하시오.

 

======================================================================================================

풀이법

파라미터로 받은 문자열 s 의 길이를 n 이라 하자.

n 번째 문자부터 순서대로 회문이 가능한지 테스트한다. (1 과 n, 2 와 n-1 . . . k 와 n - k - 1 을 차례대로 비교한다)

최소 크기의 회문의 길이를 알아 낼 수 있다.

 

이번 알고리즘은 원리는 간단하여 문자열을 잘 처리할 수 있는가를 알아보는 알고리즘 문제였다.

문제를 받고 5분간은 멍해있었으나 조금만 생각하니 간단하게 구현이 가능하였다.

 

======================================================================================================

소스코드

 

 public static int answer(String s){
              
        for(int i = s.length();; i++){
            boolean flag = true;
            for(int j = 0; j < s.length(); j++){
                if((i - j - 1) < s.length()){
                    if(s.charAt(j) != s.charAt(i - j - 1)){
                        flag = false;
                        break;
                    }
                }
            }
            if(flag) return i;
        }
       
    }