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

가장 긴 팰린드롬

문제 링크 : 가장 긴 팰린드롬

문제 설명

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

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

제한 사항

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

입출력 예

s	answer
"abcdcba"	7
"abacde"	3

풀이 방법

• 앞뒤를 뒤집어도 똑같은 문자열 중에 가장 긴 길이를 찾는 것이 문제인데, 앞뒤를 뒤집어도 똑같다는 것은 가운데 문자를 기준으로 좌우가 같다는 것이다. 그리고 주의해야 할 것이 가운데 문자가 하나일 수도 있지만, 만약에 연속된 문자가 같은 경우에는 가운데 문자가 2개일 수도 있어서 그 기준을 잘 잡아야 할 것 같다.
• 따라서 모든 문자를 순회하면서 그 문자를 기준으로 좌우를 검사하면서 가장 긴 팰린드롬을 검사하고, 그 문자가 다음 문자랑 같다면 그 두 문자를 기준으로 좌우를 검사하면서 가장 긴 팰린드롬을 검사하는 방식을 통해서 정답을 구했다.
• 팰린드롬을 검사하는 방식은 기준 문자 k를 기준으로 k-i, k+i이 동일한지 검사하면서 i를 키워나가는 식으로 했다.
  -> 이러한 문제 풀이는 최악의 경우 O(N^2)의 시간복잡도가 걸릴 것으로 예상했고, N이 최대 2,500이기 때문에 알맞은 알고리즘이라고 생각했다.

구현

#include <iostream>
#include <string>

using namespace std;

int solution(string s)
{
    int answer = 0;
    
    for(int i = 0; i < s.size(); i++){
        int k = 1;
        
        while (i - k >= 0 && i + k < s.size() && s[i - k] == s[i + k]){
            k++;
        }
        
        if (2 * (k - 1) + 1 > answer){
            answer = 2 * (k - 1) + 1;
        }
        
        if(s[i] == s[i + 1]){
            k = 1;
            while (i - k >= 0 && i + 1 + k < s.size() && s[i - k] == s[i + 1 + k]){
                k++;
            }
            
            if(2 * (k - 1) + 2 > answer){
                answer = 2 * (k - 1) + 2;
            }
        }
    }

    return answer;
}