[C++/PGS] Lv.3 : 가장 긴 팰린드롬 (투포인터/중심확장)

 

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

프로그래머스

---

프로그래머스 레벨3 팰린드롬 문제

여러 방법으로 풀이할 수 있다.

대표적으로 dp, 혹은 삼중 반복문으로 해결하는 것 같은데

나는 투포인터로 해결했다.

 

중심에서부터 투포인터를 양옆으로 보내면서 서로 값이 같은지 검사했는데,

GPT가 이런 방식을 중심 확장(Center Expansion) 기법이라고 알려줌!!

 

 

나의 풀이

#include <iostream>
#include <string>
using namespace std;
int solution(string s)
{
    int answer=1;
    int n = s.length();
    for(int i=0; i<2*n-1; ++i){
        int left = i / 2;
        int right = left + (i % 2);
        while (left >= 0 && right < n && s[left] == s[right]) {
            answer = max(answer, right - left + 1);
            left--;
            right++;
        }
    }

    return answer;
}