(프로그래머스 c++)가장 긴 팰린드롬

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 abcdcba이면 7을 return하고 abacde이면 3을 return합니다.

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

---

입출력 예

s                                                                            answer

abcdcba	7
abacde	3

 

팰린드롬을 찾기 위해 s의 가운데부터 탐색을 시작한다.

size = s의 길이, mid = s의 가운데를 나타낸다.

 

우선 size가 1 이하라면 size를 그대로 리턴해준다.

 

while문을 통해 size가 0이 될 때까지 반복.

가장 긴 팰린드롬을 찾아야 하므로 s의 길이부터 탐색을 하도록 한다.

check 변수를 통해 팰린드롬 여부를 확인한다.

mid = size / 2로 하여 s의 중간 부분을 가리킨다.

size가 홀수냐 짝수냐에 따라 탐색을 다르게 한다.

abba인 경우 4를 리턴해야 하므로, 홀수일 때와 다르게 탐색을 한다.

 

size == 홀수라면

for문을 통해 0 ~ mid 까지 왼쪽 부분(left)을 mid의 오른쪽 부분(i + mid * 2 - left)과 비교한다.

다르다면 check를 false로 하고 break.

check == true라면 현재 size가 가장 긴 팰린드롬을 나타내므로 size를 리턴한다.

 

size == 짝수라면

마찬가지로 for문을 통해 왼쪽 부분과 오른쪽 부분을 검사한다.

단, 짝수이므로 오른쪽 부분에서 -1을 해주어 비교를 한다.

 

#include <iostream>
#include <string>

using namespace std;
int solution(string s)
{
    int size = s.size(), mid = 0;
    
    if(size <= 1)
        return size;
    
    while(size > 1)
    {
        for(int i = 0; i <= s.size() - size; i++)
        {
            bool check = true;
            mid = size / 2;
            
            if(size % 2) // odd
            {
                for(int left = 0; left < mid; left++)
                {
                    if(s[left + i] != s[i + mid * 2 - left])
                    {
                        check = false;
                        break;
                    }
                }
            }
            else
            {
                for(int left = 0; left < mid; left++)
                {
                    if(s[left + i] != s[i + mid * 2 - 1 - left])
                    {
                        check = false;
                        break;
                    }
                }
            }    
            if(check)
                return size;
        }
        size--;
    }
}