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

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

문제 파악

어려운 점

타임아웃을 해결하기 위해 노력했다 😅

문자열을 순회하며 주어진 문자열의 펠린드롭 여부를 모두 조사하게 되면... 🔥Timeout🔥

펠린드롭인지 조사할 때 최적화를 덜 해서 그런지 모르겠지만,
substring을 통해 문자열을 추출하고, 아래와 같이 구현하면 채점 시 시간이 초과된다.

 

for (int from = 0; from < s.length(); from++) {
    for (int to = from; to < s.length(); to++) {
        String targetStr = s.substring(from, to + 1);
        if (isPalindrome(targetStr)) {
            .. 생략
        }
    }
}

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

 

 

위 구현 방법 대신 이차원 배열 을 사용하여 Memorization을 사용하였다.

 

풀이

가장 중요한 이차원 배열의 의미와 데이터 업데이트 과정을 정리 해 보도록 하자

 

이차원 배열의 의미

DP[i][j] : 구간 [i,j] 까지의 펠린드롭 길이

모든 DP 문제가 그렇 듯 1️⃣ 초기값 삽입 2️⃣ 값 업데이트를 진행하자!

 

업데이트 과정

 1️⃣ 초기값 삽입

시작과 끝이 같은 경우 ( ex. "a", "b") 의 펠린드롭 길이는 1이므로 초기값을 설정한다.

DP[0][0] = DP[1][1] ... = DP[N-1][N-1] = 1

 

2️⃣ 값 업데이트

만약 [i,j] 구간이 펠린드롭이 아니라면 -1을 저장, 펠린드롭이 맞다면 펠린드롭의 길이를 저장하도록 구현하였다.
이를 N-1 번째 인덱스부터 진행하도록 한다.

 

1. DP[i,j] = -1 인 경우 (펠린드롭 X)
   • 시작점 i의 문자와 끝점 j의 문자가 같지 않으면 당연히 펠린드롭이 아니다.
   • 시작점 i의 문자와 끝점 j가 같더라도, [i+1, j-1] 이 펠린드롭이 아니라면, 이는 펠린드롭이 아니다!
2. DP[i,j] = 2 (펠린드롭 O)
   • 시작점 i의 문자와 끝점 j가 같고, i와 j 인덱스의 차이가 1일 때 2로 업데이트 해 준다.
3. DP[i,j] = DP[i+1][j-1] + 2 (펠린드롭 O)
   • 사이 값인 DP[i+1][j-1]에 펠린드롭 길이가 저장되어 있으므로, 시작점과 끝점의 개수인 2를 DP[i+1][j-1]에 더해주자

 

코드

import java.util.Arrays;

public class Solution {
    public int solution(String s) {
        int len = s.length();
        int[][] palindrome = new int[len][len];
        for (int[] p : palindrome) {
            Arrays.fill(p, -1);
        }
        for (int mid = 0; mid < s.length(); mid++) {
            palindrome[mid][mid] = 1;
        }
        int max = 1;
        for (int from = len - 1; from >= 0; from--) {
            for (int to = from + 1; to < len; to++) {
                if (s.charAt(from) != s.charAt(to)) {
                    continue;
                }
                int result = -1;
                if (to - from == 1) {
                    result = 2;
                } else if (palindrome[from + 1][to - 1] != -1) {
                    result = palindrome[from + 1][to - 1] + 2;
                }
                max = Math.max(max, result);
                palindrome[from][to] = result;
            }
        }
        return max;
    }

}