[ 프로그래머스 가장 긴 팰린드롬 (Lv3) ] (C++)

프로그래머스의 가장 긴 팰린드롬(Lv3) 문제이다.

[ 문제풀이 ]

주어진 문자열에서 가장 긴 팰린드롬 문자열의 길이를 찾아서 return 해야 하는 문제이다.

그럼, 간단한 예시를 통해서 문제에 접근해보자.

"CABAC" 라는 문자열을 가지고 한번 알아보자.

지금부터 간단하게 수식을 이용해서 팰린드롬 문자열을 판단해보자.

F[A][B] = true / false 라는 수식을 사용할 것인데,

F[A][B] = true의 의미는 A번 문자부터 B번문자까지는 팰린드롬 문자열이 맞습니다 를 의미하고

F[A][B] = false의 의미는 A번 문자부터 B번문자까지는 팰린드롬 문자열이 아닙니다 를 의미한다.

그럼 C A B A C 라는 문자열을 가장 앞에 있는 문자부터 1번 문자 ~ 5번 문자라고 생각하고 진행해보자.

(실제 코드에서는 0번 ~ 4번 Index에 해당하는 문자들입니다 ! )

여러가지 상황들을 통해서 한번 계산을 진행해보자.

#Case1 : A = B 인경우 - 길이가 1인 팰린드롬 문자열

F[A][B]를 통해서, A번쨰 문자부터 B번째 문자까지가 팰린드롬 문자열인지 확인을 할 건데, 만약, A = B인경우이다.

예를 들어서 F[1][1] , F[2][2] 이런 경우들이다.

즉, 풀어서 말하면, "A번 문자부터 A번 문자까지가 팰린드롬 문자열인가?" 를 묻고 있는 것이다.

모든 문자는 그 문자 하나만으로 팰린드롬 문자열이다.

즉 ! A = B인 경우에는 F[A][B] = true 가 성립하게 된다.

F[1][1] = F[2][2] = F[3][3] = F[4][4] = F[5][5] = true

#Case2 : B = A + 1 인 경우 - 길이가 2인 팰린드롬 문자열

이제는, 딱 붙어있는 2개의 문자열을 알아보자.

F[A][B]에서 B = A+1이니, F[A][A + 1]이 되고, F[1][2] , F[2][3] , F[3][4] ... 와 같은 경우를 의미한다.

과연 어떤 경우에 팰린드롬 문자열일까 ??

F[1][2]인 경우, [ C A ] 를 나타낸다. 팰린드롬 문자열이 아니다.

F[2][3]인 경우, [ A B ] 를 나타낸다. 팰린드롬 문자열이 아니다.

마찬가지로, F[3][4] , F[4][5] 모두 팰린드롬 문자열이 아니다.

딱 붙어있는 길이가 2인 문자열에서, 그 문자열이 팰린드롬 문자열이 되기 위해서는 그 2개의 문자가 같아야 한다.

그러지 않으면 절대로 팰린드롬 문자열이 될 수 없다.

예를 들어서 "AA", "BB" 이런식으로 서로 같은 문자로만 이루어져 있어야 팰린드롬 문자열이 된다.

따라서 우리가 하고 있는 "CABAC"라는 문자열에서 길이가 2인 팰린드롬 문자열은 없다.

#Case3 : 길이가 3이상인 팰린드롬 문자열

이제부터는 본격적으로 팰린드롬 문자열을 찾아볼 것이다.

길이가 1, 2인 팰린드롬 문자열을 찾아봤으니 그 이상인 3, 4, 5인 팰린드롬 문자열을 찾아보자.

가장 먼저 길이가 3인 팰린드롬 문자열을 찾아보자.

먼저, "CABAC"에서 길이가 3인 문자열을 모두 적어보자.

1. CAB

2. ABA

3. BAC

이렇게 3개가 나올 수 있다. 지금부터는 위에서 했던 Case1, 2와 다르게, 수식을 이용하고 방법을 생각하면서 조금 더 효율적으로 팰린드롬 문자열을 찾아보자.

지금부터는 다음과 같은 순서대로 팰린드롬 문자열인지 찾아볼 것이다.

1. 주어진 문자열에서, 가장 첫 문자와 가장 마지막 문자를 찾는다.

2. 1에서 찾은 2개의 문자가 서로 같은 문자인지 찾는다.

3. 나머지 그 사이에 있는 문자열이 팰린드롬 문자열인지 확인한다.

위의 순서대로 한번 진행을 해보자.

가장 먼저, 첫 번째 경우인 CAB를 확인해보자

1. 가장 첫 문자 = C , 가장 마지막 문자 = B

2. 가장 첫 문자와 가장 마지막 문자가 서로 다른 경우이다. 이 경우에는 절. 대. 로. 팰린드롬 문자열이 될 수가 없다.

왜그럴까 ?? 팰린드롬 문자열이라는 것은, 앞뒤가 서로 똑같은 형태로 이루어져 있는 문자열을 의미하는데, 가장 첫 문자와 가장 마지막 문자가 다른 것이다. 그럼 팰린드롬 문자열이 될 수 있을까? 절대로 될 수가 없다.

즉 ! 팰린드롬 문자열이 되기 위해서는 "가장 첫 문자와 가장 마지막 문자가 반드시 같아야 한다".

그럼 두 번째 경우인 ABA를 확인해보자.

1. 가장 첫 문자 = A , 가장 마지막 문자 = A

2. 가장 첫 문자와 가장 마지막 문자가 서로 같은 경우이다.

이 경우에는, "팰린드롬 문자열일 가능성이 있는 문자열이므로, 나머지도 체크"를 해봐야 한다.

그럼, 이제 ABA에서 가장 첫 문자와 가장 마지막 문자를 뺀 나머지 문자들만 확인을 할 것이다.

나머지 문자들을 확인했을 때, 해당 문자열이 팰린드롬 문자열이라면 ? 해당 문자열은 팰린드롬 문자열이 되는 것이다.

왜냐하면, [ 어떤문자 ][ 팰린드롬 문자열 ][ 어떤문자 ] 의 형태로 이루어져 있는 꼴에서, '어떤 문자'가 서로 같은

문자이기 때문에, 위의 전체 문자열은 팰린드롬 문자열이 되는 것이다.

그럼 확인해보자. 나머지 문자로는 'B' 하나가 있다. 'B'는 팰린드롬 문자열일까 ? Case1에서 구했듯이, 모든 문자는 그 하나만으로 팰린드롬 문자열이다.

따라서 ! 'ABA'라는 문자열은 팰린드롬 문자열이 되는 것이다.

마지막 경우인 CAB를 확인해보자. 가장 첫 문자와 마지막 문자가 다르므로 절대로 팰린드롬 문자열이 아니다.

그럼 우리는 위의 3가지 경우에서 또 하나의 수식을 채울 수 있다.

F[2][4] = true.

그럼 길이가 4인 팰린드롬 문자열을 찾아보자.

CABAC에서 길이가 4인 문자열은, CABA와 ABAC가 있다.

그런데 딱 봐도, 위의 2개의 문자열 모두 가장 첫 문자와 가장 마지막 문자가 다르다. 그래서 위의 2개의 문자열 모두 팰린드롬 문자열이 될 수 없다. 따라서 pass.

길이가 5인 팰린드롬 문자열을 찾아보자.

길이가 5인 문자열로는 CABAC 하나만 존재한다.

1. 가장 첫 문자 = C , 가장 마지막 문자 = C

2. 가장 첫 문자와 가장 마지막 문자가 동일하므로 팰린드롬일 가능성이 있다.

3. 나머지 문자를 확인하니 'ABA'인데, 이는 우리가 길이가 3인 팰린드롬 문자열을 구할 떄, 이미 팰린드롬 문자열이라고

   확인한 문자열이다.

따라서 위의 문자열은 팰린드롬 문자열이다.

이런식으로 구할 것인데, 이제는 팰린드롬 문자열을 구하는 보다 일반적인 이야기를 조금 해보자.

과정은 위와 같이 크게 3가지로 나누면 된다.

1. Case1을 진행. (길이가 1인 팰린드롬 문자열 찾기)

2. Case2를 진행. (길이가 2인 팰린드롬 문자열 찾기)

3. Case3을 진행. (길이가 3이상인 팰린드롬 문자열 찾기)

인데 , Case3에 대해서 조금 더 이야기를 해보자.

간단하게, 문자열이 시작하는 문자의 번호를 Start번, 끝나는 문자의 번호를 End번이라고 가정해보자.

그리고 길이가 K인 팰린드롬 문자열을 계산한다고 가정해보자.

그럼, 먼저 End의 값을 계산해보면, Start + K - 1 이 된다.

예를 들어서 길이가 3인 팰린드롬 문자열을 찾을 때, 시작하는 문자의 번호가 1번이라면, 길이가 3인 문자열은, 1번 2번 3번 문자로 이루어진 문자열이 되는데, 이 때 마지막 문자의 번호인 3번은 1 + 3 - 1 이 되기 때문이다.

End = Start + K - 1.

그리고 그 2개의 문자를 확인하는 것이다.

String[Start] == String[End] ?

만약 같다면 우리가 확인해야 할 것은, F[Start + 1][End - 1] == true ? 이를 확인해 주면 된다.

[ 소스코드 ]

#include <string>
 
using namespace std;
 
bool DP[2510][2510];
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
int solution(string s)
{
    int answer = 1;
    for (int i = 0; i < s.length(); i++) DP[i][i] = true;
    for (int i = 0; i < s.length() - 1; i++)
    {
        if (s[i] == s[i + 1])
        {
            DP[i][i + 1] = true;
            answer = 2;
        }
    }
 
    for (int Len = 3; Len <= s.length(); Len++)
    {
        for (int Start = 0; Start <= s.length() - Len; Start++)
        {
            int End = Start + Len - 1;
 
            if (s[Start] == s[End] && DP[Start + 1][End - 1] == true)
            {
                DP[Start][End] = true;
                answer = Max(answer, Len);
            }
        }
    }
 
    return answer;
}