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

프로그래머스

 

• 투 포인터 알고리즘을 통해 팰린드롬의 길이를 찾아나가면 되는 문제
• 주의해야할 건 길이가 짝수일 때와 홀수일 때 왼쪽 포인터의 시작 지점이 다르다는 것

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// 팰린드롬 찾기
// 투포인터를 활용해서 특정 인덱스 기준으로 좌우로 늘리면서 체크하면 될듯
// 문제 설명에는 팰린드롬의 길이가 홀수인 경우만 나와있지만 짝수인 경우도 고려해야함
// 이 경우엔 좌 -1, 우를 기준으로 늘려나가면 될듯

// 팰린드롬 찾고 길이 구하기
int FindPalindrome(string s, int left, int right) {
    while(s[left] == s[right] && left >= 0 && right < s.size()) {
        // 조건이 맞으면 좌우로 하나씩 늘리기
        left--;
        right++;
    }
    
    return right - left - 1;
}

int solution(string s)
{
    int answer = 0;
    
    for(int i = 0; i < s.size(); i++) {
        // 홀수 팰린드롬 길이
        int oddLength = FindPalindrome(s, i, i);
        // 짝수 팰린드롬 길이
        int evenLength = FindPalindrome(s, i - 1, i);
        
        // 더 긴거
        int longerLength = max(oddLength, evenLength);
        answer = max(answer, longerLength);
    }

    return answer;
}

 

백준에서 비슷한거 푼 적 있는거 같은데...