[Java] 가장 긴 펠린드롬

programmers.co.kr/learn/courses/30/lessons/12904

코딩테스트 연습 - 가장 긴 팰린드롬

문제 설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

입출력 예

s	answer
"abcdcba"	7
"abacde"	3

입출력 예 설명

입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2
2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.

---

class Solution
{
    static int count=1;
    public int solution(String s)
    {
        int answer = 0;
        int len = s.length();
        for(int i=0; i<len; i++){
            checkP(s, i, 1);
            if(i<len-1 && s.charAt(i)==s.charAt(i+1)){
                checkPeven(s,i,1);
            }
        }
        answer = count;
        return answer;
    }
    private static void checkP(String s, int idx, int len){
        if(idx-len < 0 || idx+len >= s.length()) {
            count = Math.max(count, len*2 -1);
            return;
        }
        if(s.charAt(idx-len) == s.charAt(idx+len)){
            checkP(s, idx, len+1);
        }else{
            count = Math.max(count, len*2 -1);
        }
    }
    private static void checkPeven(String s, int idx, int len){
        
        if(idx-len < 0 || idx+1+len >= s.length()) {
            count = Math.max(count, (len+1)*2-2);
            return;
        }
       
        if(s.charAt(idx-len) == s.charAt(idx+1+len)){
            checkPeven(s, idx, len+1);
        }else{
            count = Math.max(count, (len+1)*2-2);
        }
            
        
    }
}

문제를 풀면서 하나의 인덱스를 기준으로 양 옆의 글자들을 비교해가면서 펠린드롬을 구하는 방식을 선택했다. 

 

그러나 중간에 몇몇개의 히든 테스트 케이스에서 실패가 뜨고말았다..!

 

다시 문제를 확인해보니 별 문제가 없어보였지만 역시나 내 생각에 오류가있었다.

 

하나의 인덱스만을 기준으로 양 옆의 글자들을 확인하면 무조건 답은 홀수가 나오게된다. => checkP 메소드는 이를 기준으로 작성된 것입니다.

 

그러나 짝수개일 경우도 생각해보니 가능할 것 같아 checkPeven메소드를 추가하여 짝수일때의 값도 구해보았다.

 

그러니 이제서야 통과가 되었다

 

혹시나 이 문제를 갖고 고민중이라면 짝수개일때도 고려해야함을 생각해봤으면 좋겠다!