[Lv.3] 가장 긴 팰린드롬

문제 설명

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

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

제한사항

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

입출력 예

문제 풀이

이 문제는 통과된게 신기할 정도로 무작정 풀었던 것 같다.
문자열의 첫 부분과 끝 부분의 기준을 잡고 길이를 하나씩 줄여나가면서
해당 부분들의 char 값이 같다면 팰린드롬을 검사하는 방식이다.

풀이 코드

class Solution {
    public int solution(String s) {
        int answer = 1;

        for (int i = 0; i < s.length(); i++) {
            for (int j = s.length() - 1; j > i; j--) {
                if (s.charAt(i) == s.charAt(j)) {
                    String subString = s.substring(i, j + 1);
                    if (isPalindrome(subString)) {
                        answer = Math.max(answer, subString.length());
                        break;
                    }
                }
            }
        }
        return answer;
    }

    private boolean isPalindrome(String s) {
        for (int i = 0; i < (s.length() / 2); i++) {
            if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }
}

DP 문제 풀이

DP 풀이 방식은 다른 분의 풀이 코드를 참조했다.
먼저, 문자열 길이 x 문자열 길이 의 dp 2차원 배열을 생성한다.
다음으로, 1자리 숫자들은 그 자체로 팰린드롬 이므로 dp[index][index] 위치에 1을 기입해준다.
그리고, 2자리 숫자들은 붙어있는 문자들을 비교하여 팰린드롬 이라면 dp[index][index+1] 위치에 1을 기입해준다.
마지막으로, 3자리 이상 숫자들은 3부터 문자열 길이 만큼 증가하면서 해당 문자열의 첫번째 값과 마지막 값을 비교하고 같다면 dp를 참조하여 내부에 있는 문자열이 팰린드롬인지 확인하게 된다.

DP 풀이 코드

class Solution {
    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 = k;
                }
            }
        }

        return answer;
    }
}