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

문제 출처: https://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는 알파벳 소문자로만 구성

문제 풀이

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        int max = 1;
        for(int i = 0; i < s.length(); i++) {
            for(int j = 0; j < s.length() - i; j++) {
                if(palindrome(s, i, j)) {
                    max = max < s.length() - i - j ? s.length() - i - j : max;
                    if(j == 0)
                        return max;
                }
            }
        }
        return max;
    }
    
    public boolean palindrome(String temp, int front, int back) {
        int i = 0;
        for(int j = 0 + front; i < (temp.length() - back - front) / 2; j++) {
                if(temp.charAt(j) != temp.charAt(temp.length() - i - 1 - back)) {
                    return false;
                }
            i++;
           }
        return true;
    }
}

이 문제의 핵심은 효율성 테스트에서 시간초과를 회피하는 것이다.

가장 긴 팰린드롬을 확인하는 패턴은 주어진 문자열을 앞뒤로 자르면서 확인하는 것이다.

앞을 0으로 잘랐을때 뒤는 0 ~ 9까지 자름
앞을 1로 잘랐을때 뒤는 0 ~ 9까지 자름
앞을 2로 잘랐을때 뒤는 0 ~ 9까지 자름
.
.
.
이런식으로 쭉 자르면 된다.

ex) 앞을 1로 잘랐을때 뒤는 0 ~ 9까지 자름

"abcdcba" => "a" + "bcdcba"
"abcdcba" => "a" + "bcdcb" + "a"
"abcdcba" => "a" + "bcdc" + "ba"
.
.
.

앞뒤 자르고 남은 substring이 팰린드롬인지 확인해주면되는데

이때 substring() 또는 reverse() 메소드를 사용하게되면 시간 복잡도적으로 비용이 발생하기 때문에 두 메소드를 사용한다면 정확도 테스트를 다 통과 하여도 효율성 테스트를 통과할 수 없다.

substring()과 reverse를 사용하여 풀고 같은 로직을 두 메소드를 없애고 구현하기 위해 바꾸다 보니 palindrome() 메소드의 for 문이 조금 어색한데 while문으로 짜면 더 직관적일것 같다.