[알고리즘] 회문찾기- java

1. 회문이란?
2. 문제
3. 회문찾기 아이디어
4. 코드

1.회문이란?
회문이란 거꾸로 읽어도 제대로 읽는것과 같은 문장 또는 단어다. 예를 보면 알기 쉽다.

• 소주 만병만 주소
• 기러기, 토마토

2. 문제 내가 받은 문제는 문장이 파라미터로 주어질때 문장 내에서 가장 긴 회문을 되돌려주는 풀이를 작성하는 것이다.

ex)
1) aba -> aba
2) aa -> aa
3) a -> a
4) aaaabbbb -> aaaa 또는 bbbb


3. 회문찾기 아이디어

처음에는 파라미터의 길이별로 모든 단어를 찾고 가장 긴 단어부터 회문인지 검증할까 생각했지만 시간이 너무 오래걸릴것 같아서 넘겼다.

그러다 효율성을 위해 문제를 풀 방법을 생각해냈다. 회문에서 가운데를 찾고 가운데에서 왼쪽으로 한 글자, 오른쪽으로 한 글자씩 이동하면 회문의 길이를 늘리면서 확인하는 방법이다. 이렇게해서 회문을 현재 가장 긴 길이의 회문과 길이를 비교해서 길면 교체, 짧거나 같으면 그냥 넘어간다. 예를 들어서 설명을 해보겠다.

1) 회문의 중심찾기
회문의 중심은 "aa", 또는 "aba"와 같이 두 글자나 세 글자로 시작한다. "aba"에서 회문의 중심을 'b'라고 볼수도 있지만 한 글자만 보고서는 중심인지 파악할 수 없으므로 좌우가 같은 것을 찾아야 한다.

2) 회문의 중심에서 좌우 한 글자씩 비교하기
입력받은 파라미터가 "oxabaxy"인 경우
회문의 중심은 "aba"다. 여기서 왼쪽의 글자는 'x',오른쪽 글자 또한 'x'로 같다. 다음 왼쪽의 글자는 'o',오른쪽 글자는 'y'로 다르다. 그럼 회문은 "xabax"고 이것을 초기값으로 설정한 회문값과 길이를 비교한다. 이때 초기값은 글자의 첫글자로 정했다.

글로만 보니 아주 지겹고 알아보기 힘들것이라 생각한다. 아래 코드를 작성해본다.

public String solution(String s) {
	// 초기값으로 파라미터의 첫번째 문자를 입력한다.
       String answer = String.valueOf(s.charAt(0));
       String palindrome = "";
       char[] chars = s.toCharArray();
       int initPalindromeLen =0;
       // 1. 회문의 중심을 찾는다.
       // 1-1. 이때 회문 중심의 길이는 2 또는 3이다.
       // 2. 중심부에서 왼쪽, 오른쪽으로 한칸씩 확인하면서 확장
       for(int i=0; i< s.length()-1;i++){
           // 시작 회문의 길이가 3인 경우 ex) aba
           int left = 0;
           int right = 0;
           if(i+2 <= s.length()-1&&chars[i]==chars[i+2]){
               left = i;
               right = i+2;
               initPalindromeLen = 3;
               palindrome = s.substring(left,right+1);
               palindrome = check(palindrome,chars,left,right);

           }
           if(answer.length() < palindrome.length()) answer = palindrome;

           // 시작 회문의 길이가 2인 경우 ex) aa
           if(chars[i] ==chars[i+1]){
               left = i;
               right = i+1;
               initPalindromeLen = 2;
               palindrome = s.substring(left,right+1);
               palindrome = check(palindrome,chars,left,right);

           }
           if(answer.length() < palindrome.length()) answer = palindrome;
       }
       System.out.println(s +":"+answer);
       return answer;
   }

   // 회문 확인하기 -> 왼쪽과 오른쪽 각각 한자리씩 이동하면서 동일한지 검사한다.
   private String check(String initPalindromeLen, char[] chars, int left, int right){

       while(left-1>=0 && right+1<=chars.length-1 && chars[left] == chars[right]){
           left-=1;
           right+=1;
           if(chars[left] == chars[right]){
               initPalindromeLen = chars[left]+initPalindromeLen+chars[right];
           }else {
               break;
           }
       }

       return initPalindromeLen;
   }