가장 긴 팰린드롬

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12904

---

풀이

1. abacaba
2. abaaba

첫번째 가운데에 c 가 존재하지만, 모두 팰린드롬에 해당된다.
따라서 짝수인지 홀수인지를 판단해서 풀어야한다.

우선 나의 첫번째 생각은

• 홀수인 경우

  

• 짝수인 경우

  

문자열의 문자 각각을 가운데라고 생각하고 중앙에서 확장해가는 방식, 즉 양 옆을 확인하는 방식이였다.

하지만 문자열 전체가 아닌 부분문자열 중 팰린드롬 인지를 확인하는 방식이였기 때문에,
주어진 모든 문자열에 대해 짝수와 홀수 모두 확인해야 했다.

그래서 나온 코드..

class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        if (s.length() == 1) return 1;
        for (int i=0; i<s.length(); i++) {
            int even = checkEvenPalin(s,i);
            int odd = checkOddPalin(s,i);            
            answer = Math.max(answer, Math.max(even, odd));
        }
        
        return answer;
    }
    
    int checkOddPalin(String s, int index){
        int len = 0;
        int left = index;
        int right = index;
        
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            len++;
            left --;
            right ++;
        }
        
        return len * 2 - 1;
    }
    
    int checkEvenPalin(String s, int index){
        int len = 0;
        int left = index;
        int right = index+1;
        
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            len++;
            left --;
            right ++;
        }
        
        return len * 2;
    }
}

통과 (22.83ms, 53.2MB)

뭔가 정리할 수 있을 거 같은데 ...

다른 점은 right와 return 값이므로 하나의 함수로 정리해보았다.

right는 매개변수 설정하여 짝수와 홀수마다 다른 값을 넣으면 됐고, return 값은 따로 길이를 측정하는 것이 아닌 left와 right 값으로 해결했다.

class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        if (s.length() == 1) return 1;
        for (int i=0; i<s.length(); i++) {
            int even = checkPalin(s,i,i);
            int odd = checkPalin(s,i,i+1);            
            answer = Math.max(answer, Math.max(even, odd));
        }
        
        return answer;
    }
    
    int checkPalin(String s, int left, int right){
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left --;
            right ++;
        }
        
        return right - left - 1;
    }
}

통과 (16.71ms, 53.8MB)

확실히 시간도 줄어든 모습이다.