TopCoder 전체 탐색! (회문)

본과 브루스는 대학에서 문자열 이론을 공부하고 있습니다. 브루스는 회문을 좋아합니다. 회문은 앞에부터 읽으나, 뒤에서부터 읽으나 같은 단어를 말합니다, 존은 브루스를 임의의 문자열 s로 회문을 만들어 브루스를 깜짝 놀래켜주고 싶습니다. 이때 존은 문자열 s뒤에 0개 이상의 숫자를 추가해 회문을 생성하려고 한다 존이 생성할 수 있는 가장 짧은 회문의 길이를 리턴하세요.

 

문제만 보고 역시 아직 바로 어떻게 풀어야할지 모르겠다 가장먼저 생각나는건 임의의 문자열과 회문의 길이수를 더해서 중복되는 단어를 뼤준값을 리턴해주면 되는데 어떤식으로 탐색을 해야할지 전혀 감이 안잡히더라.. abcd 면 dcba 니까 여기서 연속으로 나오는 글자 -1 해주면 되는데 d를 빼주면 되는데.. 생각이 안난다 

 

저자는 문자열 길이에 주목하라고 한다 문자열의 길이를 기준으로 잡고 문자열의 길이를 회문이 되는 문자열을 생각하면 어떤 방식으로 문제를풀어 나가라고한다 회문은 앞과 뒤를 읽어도 같은 문장이 나와야 하는 규칙이 있는데 임의 문자열 뒤에 임의로 문자를 하나 놓고 검색을 하면 쉽게 풀수 있다고 한다 

a

b

c

d

?

 

오른쪽의 물음표는 왼쪽의 문자로 자동 결정된다. 회문이 되는지는 같은 글자가 들어갈때 다른글자가 들어 있지 않은지 확인하면된다.

일단 문제의 의도가 임의의 문자열 값으로 회문할때 가장 짧은 회문의 길이를 구해야한다 ! 오케이 목적은 알았다 하지만 시작이 맹구 같다

 

 

 

 

부끄럽지만.. 이렇게 하지 않으면 이해가 안가는게 사실이다 현재 나의 위치.. 암울하다

abcd 를 입력했으니까 s.legth 는 4가 되겠고 한번식 리턴 될때 마다 i값이 증가한다 답의 문자 길이가 4니까 i가 증가 하면서 반대쪽에 있는 문자랑 다를때 플래그를 변경하는 형식이다 나는 abcd 를 입력했으니까 모두 비교하면 3이 나온다 

가장짧은 회문의 길이가 7이다  연속되는 문자는 뺴주면 회문의 규칙이 성립한다 그래서 abcd 를 입력한다고 해서 bcda가 아니라 bca 가 된다. 그래서 -1를 통해서 문자 갯수 하나의 값을 빼주는거다 .

 

어떻게 값이 리턴되는지는 알았다 만약 abcccccc를 입력하면 어떻게 될까? 그냥 직관적으로 보면 회문이 가능한 문자 갯수가 2개 필요하다 그러면 결국 답은 10이다 여기서 중복되는 8개의 문자열중에 ab를 제외하고는 다 중복이다 

 

중복되지 않은 문자 갯수는 2개니까 결국 i를 리턴하면 10이 나온다 ab가 다르니까 가장 첫뻔재 for문이 1번 2번 리턴 할것이고 나머지는 중복이니까 두번째 포문에서 8개의 문자열 길이 값만큼 돌다가 끝날것이다 그러면 현재 i에 처음에 대입된 문자열 길이숫자가  8 이고 리턴된 i값이 2이니까 더하면 10이다 

 

비슷한 문제가 나온다면 솔직히 답을 찾기는 힘들거 같다 대신 어떤 방식으로 문제를 풀어야 해결이 되겠구나 라는거 까지 이해 했지 솔직히 저자 처럼 완벽한 코딩을 할수없다 아직은.. 최대한 노력 하기로 해본다