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

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

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

class Solution
{
    public int solution(String s)
    {
        for (int len=s.length(); len>0; len--){
            for (int i=0; i<=s.length()-len; i++){
                boolean flag=true;
                int left=i;
                int right=i+(len-1);
                for (int j=0; j<len/2; j++){
                    if (s.charAt(left++)!=s.charAt(right--)){
                        flag=false;
                        break;
                    }
                }
                if (flag) return len;
            }
        }

        return -1;
    }
}

여러번 실패한 문제.. 결국 힌트를 보고 풀었다.

 

접근방법은 이렇다:

길이가 n인  팰린드롬이 있는지 살핀다=> 이때 n을 s의 총 길이부터 시작해야 한다 (최댓값을 구하는 것이기 때문에, 값을 가지면 바로 리턴하는 형태를 취한다)

이때 살피는 것은 가능한 시작점을 뽑아서, 시작점과 끝점을 각각 오른쪽, 왼쪽으로 이동시켜주면서 서로에 대해 N/2번 비교를 수행한다. (길이가 N인 팰린드롬의 경우 양쪽에서 비교할 경우 N/2번의 비교 연산이 필요하다)

이때 비교 수행 중에 서로 다른 문자가 있으면 flag 값을 주어 그 시작점에서부터 시작하는 그 길이의 팰린드롬은 없음을 알린다. flag값이 true이면 그 길이의 팰린드롬 값은 있으므로, 바로 그 길이를 리턴해주면 된다.

 

잘 생각해보면 어렵지 않은 문제같은데, 막상 풀어보니 어렵다..