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

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

프로그래머스

 

팰린드롬이란 뒤집어도 같은 문자열이 되는 것을 말한다. aba , aaa 같은 경우가 팰린드롬이다.

 

나 같은 경우는 이 문제를 단순 반복문으로 풀어냈는데 효율성 테스트도 잘 통과되었다. 그러나 마나커? 마나허? 알고리즘을 사용하는 문제라고 한다. 다음에 한번 정리를 하는 것으로 하자

 

#include <iostream>
#include <string>
using namespace std;
int solution(string s)
{
    int answer = 1;
        
    if(s.size() == 1) return 1;
    
    for(int i = 0; i < s.size(); i++){
        int left = i - 1;
        int right = i + 1;
        int tmp = 0;
        while(left > -1 && right < s.size()){
            if(s[left] == s[right]) tmp++;
            else break;
            
            left--;
            right++;
        }
        
        answer = max(answer, tmp * 2 + 1);
        
        left = i - 1;
        right = i;
        tmp = 0;
        while(left > -1 && right < s.size()){
            if(s[left] == s[right]) tmp++;
            else break;
            
            left--;
            right++;
        }
        
        answer = max(answer, tmp * 2);
    }
    return answer;
}