[프로그래머스] 가장 긴 팰린드롬

링크

[프로그래머스] 가장 긴 펠린드롬

문제

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(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합니다.

과정

1. 처음에 문제를 읽고 완전 탐색으로 하려는 미친 생각을 잠시 했지만 최대 길이가 2500인 것을 보고 포기
2. 다른 블로그 [jaeyoon-95.님 블로그] 글을 참고하니 순회하며 가운데 값을 기준으로 좌우측으로 확장하면서 검사하면 간단한 문제였다...!!!
3. 홀수는 정석대로 확장, 짝수는 그다음 문자가 같을 때만 흘러가게 했다.

코드

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        for(int i=0; i<s.length(); i++){
            //홀수
            answer = Math.max(answer, oddP(s,i));
            //짝수
            answer = Math.max(answer, evenP(s,i));
        }
        
        
        return answer;
    }
    private int oddP(String str, int idx){
        int left = idx - 1;
        int right = idx + 1;
        int length = 1;
        while(true){
            if(left < 0 || right >= str.length()) return length;
            char cLeft = str.charAt(left);
            char cRight = str.charAt(right);
            
            if(cLeft != cRight) return length;
            
            length += 2;
            left--;
            right++;
        }
    }
    
    
    private int evenP(String str, int idx){
        if(idx == str.length() -1) return 1;
        if(str.charAt(idx) != str.charAt(idx+1)) return 1;
        
        int left = idx - 1;
        int right = idx + 2;
        int length = 2;
        while(true){
            if(left < 0 || right >= str.length()) return length;
            char cLeft = str.charAt(left);
            char cRight = str.charAt(right);
            
            if(cLeft != cRight) return length;
            
            length += 2;
            left--;
            right++;
        }
    }
}