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

문제 설명

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

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

제한사항

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

---

풀이

15분
팰린드롬의 조건을 양쪽 대칭이라고 생각했을 때, 처음에 홀수 경우만 생각하여 해맸다. 팰림드롬의 문자 개수가 짝수일 경우까지 고려한 코드를 추가하여 풀어주었다.

코드

// 10:58 ~ 11:14
#include <iostream>
#include <string>

using namespace std;

int solution(string s)
{
    int max_len = 0;
    for(int i =0; i < s.size(); ++i){
        int len;
        for(len = 0; i + len < s.size() && i - len >= 0; ++len){
            if(s[i + len] != s[i - len]) break;
        }
        max_len = max(max_len,len * 2 - 1);
        if(i != s.size() - 1 && s[i] == s[i + 1]){
            for(len = 0; i + len + 1 < s.size() && i - len >= 0; ++len){
                if(s[i - len] != s[i + len + 1]) break;
            }
            max_len = max(max_len,len * 2);
        }
    }
    return max_len;
}