프로그래머스 - 가장 긴 팰린드롬

프로그래머스 - 가장 긴 팰린드롬

팰린드롬 문자열이란 문자열을 뒤집은 결과가 기존 문자열과 같은 문자열이다.

즉 예를 들어, "abcdedcba" 는 길이가 9가 되는 팰린드롬 문자열이다.
또한 aba는 길이가 3인, aaaa는 길이가 4인, abcde길이가 1인 팰린드롬 문자열을 포함한 문자열이다.

위 문제는 주어진 문자열 중 가장 긴 팰린드롬 문자열을 찾아내면 된다.

풀이 방법

0부터 시작하고, n-1까지가 길이인 주어진 문자열을 1부터 n-2까지 순회해줍니다. (mid)

mid를 기준으로 left_idx(mid)와 right_idx(mid)를 둡니다.

• 만약 s[left_idx - 1]과 s[left_idx]가 같다면 left_idx를 1감소 (다를 때 까지 감소)
• 만약 s[right_idx + 1]과 s[right_idx]가 같다면 right_idx를 1증가 (다를 때 까지 증가)

left_idx는 mid를 기준으로 왼쪽으로만 감소하고, right_idx는 그 반대입니다.
감소/증가를 진행 하면서 s[left_idx]과 s[right_idx]가 다르다면 break해줍니다.

이 과정을 1 ~ n-2까지 진행해주면서 answer 값을 최대 값으로 업데이트 해주면 됩니다.

코드는 아래와 같습니다.

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

int solution(string s)
{
    int answer = 0;
    int n = s.size();
    if(s.size() == 1)
        return 1;
    else if(s.size() == 2) {
        if(s[0] == s[1])
            return 2;
        else
            return 1;
    }
    
    for(int i=1;i<n-1;i++) {
        int count = 1;
        char mid_char = s[i];
        char left_char, right_char;
        left_char = right_char = mid_char;
        int left_idx, right_idx;
        left_idx = right_idx = i;
        // 해당 예외처리 안하면 "aaaa" 같은 문자열에서 올바른 답이 안나올 수 있음
        while(1) {
            if(left_char != s[left_idx - 1]) 
                break;
            left_char = s[left_idx - 1];
            left_idx = left_idx - 1;
            count++;
        }
        while(1) {
            if(right_char != s[right_idx + 1]) 
                break;
            right_char = s[right_idx + 1];
            right_idx = right_idx + 1;
            count++;
        }
        while(1) {
            if(left_char != right_char)
                break;
            if(left_idx - 1 < 0 || right_idx + 1 > n - 1)
                break;
            if(s[left_idx - 1] != s[right_idx + 1]) 
                break;
            
            left_char = s[left_idx - 1];
            right_char = s[right_idx + 1];
            left_idx--;
            right_idx++;
            count+=2;
        }
        answer = max(count, answer);
    }
    
    return answer;
}