탑코더(TopCoder) 알고리즘 - The Panlindrome

The Panlindrome

The Panlindrome (회문) - 문제 링크 (탑코더 로그인 필요함)

한줄요약) 주어진 문자열 뒤에 (0개 이상의) 문자를 추가하여, 가장 짧게 회문이 되는 경우의 문자열 길이를 구하시오. (회문은 앞부터 읽으나 뒤부터 읽으나 같은 문자열을 말합니다. 예를들면 리효리)

ex1) 주어진 문자열이 abb이면 가장 짧게 회문이 되는 경우는 abba이고 문자열 길이 4가 정답

ex2) 주어진 문자열이 abcba이면 이미 회문이 되므로 문자열 길이는 5가 정답

문제 풀이

먼저 주어진 문자열이 회문인지 확인합니다. 

주어진 문자열이 a b c 인 경우 0번째와 n번째 문자가 같은지 확인합니다. a b c

문자가 같은 경우 1번째, 2번째 . . . 의 경우를 계속 확인해보고, 아닌 경우 문자열의 길이가 1 증가 하였다고 가정 해봅니다. 어떤 글자인지는 중요하지 않습니다. 핵심은 회문을 만드는 것이 아니고, 가장 짧게 회문이 가능한 문자열의 길이를 구하는 것이기 때문입니다.

1글자 추가하였다고 가정하고 회문이 가능한지 확인합니다.

0번째와 n번째의 경우는 굳이 검사를 하지 않고 회문이 가능하다고 가정하고 생략합니다. (마치 a가 있는 것처럼)

a b c _ 

그리고 1번째와 n-1번째의 경우를 확인 해보니 회문이 불가능한 경우 입니다. 

a b c _

이번에는 1글자 더 추가해서, 총 2글자를 추가하였다고 가정하고 회문이 가능한지 확인합니다.

0번째와 n번째와, 1번째 n-1번째는 경우는 굳이 검사를 하지 않고 회문이 가능하다고 가정하고 생략합니다. 

a b c _ _ 

그리고 2번째와 n-2번째의 경우를 확인 해보니 회문이 가능한 구조입니다. 주어진 문자 abc가 가장 짧게 회문이 되는 문자열의 길이는 5가 됩니다.

a b c _ _ 

 

위와 같은 방법으로 계속해서 문자열의 길이를 하나씩 증가 시켜보고 회문이 가능한지만 확인하면 됩니다.

풀이 코드 (java)

public class ThePalindrome {
    static int find(String s) {
        int add = 0; //추가된 문자열의 길이

        for (int i = 0; i < (s.length() + add) / 2; i++) {
            //추가된 문자열의 수만큼 검사하지 않는다.
            if (i < add) { 
                continue;
            }
           //회문이 아닐 경우 문자열의 길이를 하나씩 증가시켜 본다,
            if (s.charAt(i) != s.charAt(s.length() - 1 - i + add)) {
                add++;
                i = 0;
            }
        }
        return s.length() + add;
    }
}

배운점

1. 문제의 추상화가 조금 어려웠는데, 추상화를 성공하고 나서 코드는 쉽게 나오게 됐다. 코드를 무작정 푸는 것보다 문제를 이해하고 규칙을 찾는것이 먼저임을 다시 한번 배웠다.
2. 추상화의 핵심은 회문을 구하는 것이 아닌 회문이 가능한 문자열을 구하는 것이 였는데, 리턴타입을 좀 더 자세히 봐야 겠다는 교훈을 얻었다. 리턴 타입이 문제풀이의 힌트가 될 수도 있다.