[Algorithm] Programmers :: 가장 긴 팰린드롬

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

프로그래머스

int solution(string s)
{
    int answer = 1;
    int size = s.size();
    bool isBreak = false;
 
    for (int i = 0; i < size; ++i)
    {
        for (int j = size - 1; j >= i+1; --j)
        {
            int firstIndex = i;
            int secondIndex = j;
            int standSize = secondIndex - firstIndex + 1; // 검사구간 크기.
            int count = 0;
 
            if (standSize <= answer)
            {
                break;
            }
 
            while (1) // 처음 끝 쌍비교.
            {
                if (s[firstIndex + count] == s[secondIndex - count])
                {
                    ++count;
 
                    if (count == standSize / 2)
                    {
                        answer = max(answer, standSize);
                        break;
                    }
                }
                else // 하나라도 안맞으면 바로 탈출.
                {
                    break;
                }
            }
 
            if (count == standSize / 2)
            {
                answer = max(answer, standSize);
            }
        }
    }
 
    return answer;
}

 

팰린드롬이란 뒤집어도 똑같은 문자열을 의미한다.

딱 필요한만큼만 비교를 해야 효율성테스트를 통과한다.

처음부터 완전탐색처럼 하되, 이후 남은 검사를 할 필요가 없는 경우 중단해줘야 한다.

위 코드는 말로 설명하는것보다는 그냥 예제 하나 넣어놓고 한줄씩 수행시키는게 제일 이해가 빠를거라 생각한다.