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

프로그래머스

문자열 s가 있고 s를 반대로 뒤집을 것을 s'라고 할때 s 와 s'가 같으면 이 문자열은 팰린드롬이라고 합니다.

문자열 s가 주어질 때 부분문자열중 가장 긴 팰린드롬의 길이를 구해주세요.

 

풀이방법

이 문제의 제한사항을 보면 s의 길이가 2500이하의 정수라고 나와있습니다. 즉 N * N의 속도로 풀이가 가능하다는 이야기입니다.

저는 속도의 제한이 없기 때문에 굉장히 직관적인 방법으로 풀어보았습니다.

 

풀이 방법은 아래와 같습니다.

1. 문자열의 모든 문자들을 순회합니다.

2. 현재 문자가 팰린드롬의 가장 가운대라고 가정하고 왼쪽 문자와 오른쪽 문자를 while문을 이용해서 계속 비교합니다. 

3. 이를 반복하여 가장 긴 팰린드롬을 찾으면 됩니다.

 

정답 코드

#include <string>
using namespace std;

int palindrome(string& s, int left, int right)
{
    while (left >= 0 && right < s.size())
    {
        if (s[left] != s[right])
            break;
        
        left--;
        right++;
    }
    
    return right - left - 1;
}

int solution(string s)
{
    int answer = 0;
    for (int i = 0; i < s.size(); i++)
    {
        int a = palindrome(s, i,  i);
        int b = palindrome(s, i-1, i);
        answer = max(answer, max(a, b));
    }

    return answer;
}