[프로그래머스] 가장 긴 팰린드롬 / C++

문제 설명

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

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

 

제한 조건

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

 

입출력 예

s	answer
"abcdcba"	7
"abacde"	3

 

 

코드

#include <string>
#include <vector>

using namespace std;

// d[i][j]는 s[i]부터 s[j]까지의 문자열이 팰린드롬인지를 의미함
// -1 	: 확인되지 않음
// 0	: 팰린드롬 X
// 1	: 팰린드롬 O
vector<vector<int>> d;

int dp(int start, int end, string &s)
{
    if (start >= end)
        return 1;
    // 이미 확인됐다면 결과를 리턴
    if (d[start][end] != -1)
        return d[start][end];
    if (s[start] == s[end])
        d[start][end] = dp(start + 1, end - 1, s);
    else
        d[start][end] = 0;
    return d[start][end];
}

int solution(string s)
{
    vector<int> v;
    int i, start, len;
    
    // d를 -1로 초기화
    v.resize(s.size(), -1);
    for (i = 0; i < s.size(); i++)
    {
        d.push_back(v);
    }
    // 가장 긴 팰린드롬을 찾아야하기 때문에 가장 긴 길이부터 확인
    for (len = s.size(); len > 0; len--)
    {
        for (start = 0; start + len <= s.size(); start++)
        {
            // 팰린드롬을 찾으면 길이를 리턴 (최댓값)
            if (dp(start, start + len - 1, s))
            {
                return len;
            }
        }
    }
}

 

링크

programmers.co.kr/learn/courses/30/lessons/12904

코딩테스트 연습 - 가장 긴 팰린드롬

github.com/inbdni/Programmers/blob/master/level03/%EA%B0%80%EC%9E%A5%EA%B8%B4%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC.cpp

inbdni/Programmers