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

문제

---

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

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

 

 

[제한사항]

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

 

 

풀이

---

완전탐색으로 위치에 따른 가능한 최대 팰린드롬을 찾는 방식을 사용하였고,

for(int i = s.length() - 1 ; i >= 0 ; i--){

    answer = Math.max(answer, findPalindrome(s, i, i));
    answer = Math.max(answer, findPalindrome(s, i, i + 1));
}

위 코드로 최대의 팰린드롬 길이를 저장하였다.

findPalidrome(s, i, i) 와 find(Palidrome(s, i, i+1) 두가지 경우로 하는 이유는 팰린드롬이 홀수 일 때와 짝수 일 때를 나누기 위해서다.

 

시간의 효율성을 위해서 두개의 포인터를 사용하였다.

static int findPalindrome(String s, int L, int R){

    while(L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)){
        L--;
        R++;
    }

    return R - L - 1;
}

 

위 코드가 두개의 포인터를 사용한 완전탐색을 이용해서 최대 길이의 팰린드롬을 찾아내는 코드다.

 

<전체코드>

class Solution
{
    public int solution(String s)
    {
        int answer = 1;
        
        
        for(int i = s.length() - 1 ; i >= 0 ; i--){

            answer = Math.max(answer, findPalindrome(s, i, i));
            answer = Math.max(answer, findPalindrome(s, i, i + 1));
        }
        
        return answer;
    }
    
    static int findPalindrome(String s, int L, int R){

        while(L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)){
            L--;
            R++;
        }

        return R - L - 1;
    }
}