[프로그래머스 lv3] 가장 긴 팰린드롬 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

팰린드롬의 길이가 짝수일 때, 홀수일 때를 나누어 구현할 수도 있지만 복잡한 게 싫어서 dp로 처리했다.

인덱스 i 부터 j까지의 팰린드롬 여부를 dp[i][j] (단, i <= j) 라고 할 때, 

 

1) i == j 이면 한 글자이고, 무조건 팰린드롬이므로 dp[i][j] = true가 된다.

2) i+1 == j 이면 두 글자이고, s[i] == s[j] 일 때 팰린드롬이 된다.

3) 나머지 경우들은 세 글자 이상인데, i+1 부터 j-1까지 팰린드롬이고 s[i] == s[j]이면 팰린드롬이 된다.

 

위의 세가지 사항을 고려하여 dp[i][j]를 채우면 된다.

주의할 것은 3) 번에서 dp[i][j]를 구하기 위해 dp[i+1][j-1] 값을 참조해야 하는데, 그 말인즉슨, i+1행을 i행 보다 먼저 구해놓아야 한다는 뜻이다. 따라서, 각 행을 순회할 때 더 뒤쪽의 행을 먼저 수행할 수 있도록 반복문을 구현해야 한다.

 

dp[i][j]를 구하고, dp[i][j] == true 일 때 팰린드롬 길이(j-i+1)의 최댓값을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int mx;
bool dp[2505][2505];

int solution(string s) {

    int n = s.size();
    for (int i=n-1; i>=0; i--) {
        for (int j=0; j<n; j++) {
            if (i == j) dp[i][j] = true;
            else if (i+1 == j) {
                if (s[i] == s[j]) dp[i][j] = true;
            }
            else {
                if (dp[i+1][j-1] && s[i] == s[j]) dp[i][j] = true;
            }
            if (dp[i][j]) mx = max(mx, j-i+1);
        }
    }

    return mx;
}