[프로그래머스]연습문제 : 가장 긴 팰린드롬 (level 3)(c++)

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

코딩테스트 연습 - 가장 긴 팰린드롬

 

 

 

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

using namespace std;

int get_pldr_len(const string &s, int left, int right)
{
    int pldr = right - left - 1;
    while (!(left < 0 || right >= s.size()) && s[left] == s[right])
    {
        --left;
        ++right;
        pldr += 2;
    }
    return pldr;
}

int solution(string s)
{
    int N = s.size();
    int answer = 1;
   
    /*
        각 문자를 기준으로 팰린드롬이 만들어지는지 확인하고,
        최대길이를 갱신한다.
    */
    for (int i = 0; i < N - 1; ++i)
    {

        // abba 형태 팰린드롬 : 바로 다음문자부터 대칭 시작
        if (i + 1 < N && s[i] == s[i + 1])
        {
            answer = max(get_pldr_len(s, i, i + 1), answer);
        }

        // abcba 형태 팰린드롬 : 문자 하나를 사이에 두고 그다음부터 대칭 시작
        if (i + 2 < N && s[i] == s[i + 2])
        {
            answer = max(get_pldr_len(s, i, i + 2), answer);
        }
    }

    return answer;
}

 

 

전체 문자열을 탐색하면서 i번째 또는 i + 1번째 문자열을 기준으로 팰린드롬이 만들어지는지 확인한다.

 

팰린드롬의 2가지 형태

1. abba : 가운데 문자 X

2. abcba : 가운데 문자 O

 

각각의 경우에서 기준이 되는 문자를 정하고,

왼쪽 인덱스는 줄여가고 오른쪽 인덱스는 키워가면서 대칭되는지 확인한다.

그리고 최대값 갱신하기!