[TopCoder] 회문 (Java, C#)

---

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

응용문제: 최소 길이인 회문도 구하기

---

 

문제 파악하기

1. 일단 무조건 회문이 되는 방법은 s를 거꾸로 해서 이어 붙이는 것이다.
하지만 이 방법은 최소 길이가 아니다.

2. s에서 뒤에 단어를 하나씩 붙여가며 회문인지 확인한다.
0개를 붙인 것(이미 회문인 상태)부터 하나씩 이어붙여서 확인하면 최소 회문 길이를 알 수 있다.
ex) 인덱스 번호로 0 1 2 3 4 인 5글자 단어가 있으면,
처음 0 1 2 3 4 가 회문인지 검사,
회문이 아니면 0 1 2 3 4 0이 회문인지 검사,
회문이 아니면 0 1 2 3 4 1 0이 회문인지 검사,
회문이 아니면 0 1 2 3 4 2 1 0이 회문인지 검사, 
회문이 아니면 0 1 2 3 4 3 2 1 0이 회문인지 검사한다.

3. 회문인지 아닌지 판단하는 방법은 양 끝에서부터 안쪽으로 문자가 같은지 비교한다.
검사하다가 틀리면 false를 부여하고 break한다. true인 경우 모든 검사를 통과한 것이기 때문에 회문이다.

 

전체 코드

(C#)

        static int Solution(string s)
        {
            string reverse =  new string(s.Reverse().ToArray());
            string answer = "";
            for (int i=0; i<s.Length; i++)
            {
                string checkWord = s + reverse.Substring(s.Length - i, i);
                bool check = true;
                for (int k=0; k<(checkWord.Length+1)/2; k++)
                {
                    if (checkWord[k] != checkWord[checkWord.Length - k - 1])
                    {
                        check = false;
                        break;
                    }
                    
                }
                if (check)
                {
                    answer = checkWord;
                    break;
                }
            }
            Console.WriteLine(answer);
            return answer.Length;
        }

 

(Java) 자바로 다시 풀 때는 단순하게 문자의 길이만 파악하도록 코드를 짰다.

public class ThePalindrome {
    public int find(String s) {
        int n = s.length();

        for (int i = n; ; i++) {
            boolean isPalindrome = true;
            System.out.println("i is " + i);
            for (int j = 0; j < n; j++) {
            	System.out.println("j is " + j);
            	//i는 현재 글자 수, index는 끝에서부터의 글자 index
                int index = i - j - 1;
                if (index < n && s.charAt(j) != s.charAt(index)) {
                    isPalindrome = false;
                    break;
                }
            }
            if (isPalindrome) {
                return i;
            }
        }
    }