문제

문제 설명

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

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

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

풀이1

무식하게 모든 경우의 수를 기준을 가지고 substring하면서 앞,뒤가 같은지를 검사하는 완전 탐색으로 푸니까 정확성 테스트는 모두 맞았다. 그런데 이 문제는 효율성 테스트는 시간초과가 났다.

이 풀이 방법의 헛점은 불필요(?)하게 substring을 많이 한다.
findPalindromeMaxLen(s.substring(0,idx),left_max);
findPalindromeMaxLen(s.substring(idx,length),right_max);

문자열 reverse를 해서 같은지 비교를 하기 위해서 idx 기준 왼쪽에서의 경우, 오른쪽에서의 경우 substring을 하면서 비교한다. 그리고 findPalindromeMaxLen 함수 내에서도 front와 back 비교를 위해 substring을 수행한다.

문제가 문자열 1개씩 비교하는 것보다 substring을 수행하기 위해 for문을 더 많이 사용하게 된다.

코드

class Solution
{
   private static int findPalindromeMaxLen(String substr, int max) {
        int len = substr.length();
        int mid = len/2;

        for (int i = 0; i < mid; i++) {
            String s_front = substr.substring(i,mid);
            String s_back = (len % 2 == 0) ? substr.substring(mid,len-i) : substr.substring(mid+1,len-i);
            StringBuilder sb_back = new StringBuilder(s_back);
            //System.out.println(s_front + " " + s_back);

            if( sb_back.reverse().toString().equals(s_front) ) {
                max = Math.max(max,len-(2*i));
            }
        }

        return max;
    }

    public static int solution(String s) {
        int length = s.length();

        if (length == 0)   return 0;
        if (length == 1)   return 1;

        int left_max = 1; int right_max = 1;
        for (int idx = length; idx >= 0; idx--) {
            left_max = findPalindromeMaxLen(s.substring(0,idx),left_max);
            right_max = findPalindromeMaxLen(s.substring(idx,length),right_max);
        }

        return Math.max(left_max, right_max);
    }
}

풀이2

풀이1를 보완해서 while( L >=0 && R < s.length() && s.charAt(L) == s.charAt(R) ) 각 문자 1개씩을 비교하여 길이만 return 해주도록 수정했다.

palindrome길이가 홀수일 경우와 짝수일 경우 모두 수행하여 더 긴 값을 답으로 리턴해준다.

코드

class Solution {
    public static int palindromeMaxLength(String s, int left, int right) {
        int L = left; int R = right;
        
        while( L >=0 && R < s.length() && s.charAt(L) == s.charAt(R) ) {
            L--;
            R++;
        }

        return R-L-1;
    }

    public static int solution(String s) {
        int length = s.length();
        
        int len = 1;
        for (int i = length; i >= 0; i--) {
            len = Math.max(len,palindromeMaxLength(s,i,i)); // palindrome이 홀수일때 길이
            len = Math.max(len,palindromeMaxLength(s,i,i+1)); // palindrome이 짝수일때 길이
        }

        return len;
    }
}

풀이3

백준 문제를 보면 팰린드롬을 DP로 접근하여 푼다.
그래서 DP로도 구현해보았다.

점화식은 다음과 같다.
D[i][j] == 1 : i번째 문자와 j번째 문자가 팰린드롬이면 1
D[i][j] == 0 : i번째 문자와 j번째 문자가 팰린드롬이 아니면 0

1. 1자리
   dp[i][i] = 1;
   answer = 1;

2. 2자리
   dp[i][i+1] = 1;
   answer = 2;

3. 3자리
   D[i-1][j+1] == 1 && s.charAt(i) == s.charAt(j) 이면
   dp[i][j] == 1;
   answer = 현재 팰린드롬 자리수(문제에서 k)

코드

public static int solution(String s) {
        int answer = 1;
        int len = s.length();
        char[] a = s.toCharArray();

        int[][] dp = new int[len][len];

        // 1. 1자리
        for (int i = 0; i < len; i++)
            dp[i][i] = 1;

        // 2. 2자리
        for (int i = 0; i < len-1; i++) {
            if( a[i] == a[i+1] ) {
                dp[i][i + 1] = 1;
                answer = 2;
            }
        }
        // 3. 3자리 이상
        for (int k = 3; k <= len; k++) {
            for (int i = 0; i <= len-k ; i++) {
                int j = i+k-1; // k길이 만큼 떨어진 index
                if( a[i] == a[j] && dp[i+1][j-1] == 1 ) { // 문자열이 같고, [i-1][j+1] 가 팰린드롬이라면
                    dp[i][j] = 1;
                    answer = Math.max(answer,k);
                }
            }
        }

        return answer;
    }