[Topcoder] ThePalindrome(회문)

존과 브루스는 대학에서 끈 이론을 공부하고 있다. 브루스는 회문을 매우 좋아한다. 회문은 앞과 뒤를 똑같이 읽는 단어이다. 존은 s를 취하고, 회음을 얻기 위해 s의 끝에 0개 이상의 문자를 추가함으로써 브루스를 놀라게 하고 싶어한다. 그는 회음부가 가능한 한 짧기를 원한다. 존이 생성할 수 있는 가장 짧은 회문 길이를 반환합니다.

Definition

Class:

 

ThePalindrome

Method:

 

find

Parameters:

 

string

Returns:

 

integer

Method signature:

 

def find(self, s):

 

Examples

0)

"abab"

Returns: 5

"ababa" is the shortest palindrome that John can get.

 

1)

"abacaba"

Returns: 7

Already a palindrome.

 

2)

"qwerty"

Returns: 11

All characters are different.

 

3)

"abdfhdyrbdbsdfghjkllkjhgfds"

Returns: 38

---

문자열 s를 회문으로 만들기 위해서 각 처음과 끝에서부터 문자를 하나하나 비교해야하므로 

 

전체 탐색 문제이다. 

 

#include <string>
using namespace std;

class ThePalindrome
{
    public:
    int find(string s){
        for(int i= s.size(); ; i++){
            bool flag = true;
            for(int j=0; j<s.size(); j++){
                if(s[j] != s[i-j-1] && (i-j-1) < s.size()){
                    flag = false;
                    break;
                }
            }
            if (flag) return i;
        }
    }
};

전체 코드이다. 

 

문자열(string) s를 parameter로 받고 이 s를 회문으로 만들었을 때 최종 문자열 길이(int)를 반환한다. 

 

i를 문자열 s의 길이부터 시작(문자열 끝에서부터 비교하기 위해)하여 회문을 만들기 위해 하나하나 늘려간다. 

 

    int find(string s){
        for(int i= s.size(); ; i++){

 

예를 들어 s가 abcccaa일때 먼저 a와 a를 비교한다. 일치하니까 다음으로 넘어가면 b와 a를 비교한다. 

 

일치하지 않으므로 문자열 끝에 문자를 추가한다. 

                if(s[j] != s[i-j-1] && (i-j-1) < s.size()){
                    flag = false;
                    break;

abcccaa? 

 

문자 하나가 추가되었으므로 두번째부터 비교한다.

(i-j-1) < s.size()

위 코드 때문에 이미 비교했던 문자들은 건너뛰고 특정 문자부터 비교한다. 

 

a(패싱)/bcccaa/?(패싱)

 

b와 a 여전히 불일치하므로 문자 하나를 더 추가한다. 

 

abcccaa??

 

세번째부터 비교한다. c와 a. 문자 하나 추가한다.

 

abcccaa???

            for(int j=0; j<s.size(); j++){
                if(s[j] != s[i-j-1] && (i-j-1) < s.size()){
                    flag = false;
                    break;
                }
            }
            if (flag) return i;

문자열들을 다 비교하는 for문을 break 없이 통과했으면, 문자열 길이 i를 반환한다.

 

따라서 위 과정이 반복되어 만들어지는 회문은 abcccaacccba 이다. 5개의 문자가 추가되었고, 회문 길이는 12이다.