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

1. 문제

문제 링크

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

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

입출력 예

s	answer
"abcdcba"	7
"abacde"	3

2. 풀이

단순히 완전 탐색으로 접근하면 효율성 테스트를 통과하지 못하는 문제입니다.
그렇기 때문에 팰린드롬인지 확인하는 연산의 중복을 피해야 해결할 수 있습니다.

어떻게 팰린드롬인지 효율적으로 확인할까?

const N = s.length;
const memo = [...Array(N)].map(() => [...Array(N)].map(() => -1));

const isPal = (a, b) => {
    // 길이가 1일 때
    if (a == b) return 1;

    // 길이가 2일 때
    if (a + 1 == b) return s[a] == s[b] ? 1 : 0;

    if (memo[a][b] != -1) return memo[a][b];

    // s[a] == s[b] 라면, 재귀적으로 안에있는 문자열도 팰린드롬인지 확인
    return memo[a][b] = s[a] == s[b] ? isPal(a + 1, b - 1) : 0;
};

isPal함수는 s[a] ~ s[b]의 문자열의 팰린드롬 여부를 리턴합니다.
팰린드롬은 결국 s[a](팰린드롬)s[b]으로 생각할 수 있기 때문에
s[a] == s[b]면 isPal(a + 1, b - 1)를 재호출해서 확인합니다.
그리고 그 값을 memo배열에 저장하기 때문에 중복된 요청에 대해서 재연산을 피합니다.

가장 긴 팰린드롬 찾기

outer:
for (let len = N; len >= 1; len--) {
    for (let a = 0; a <= N - len; a++) {
        if (isPal(a, a + len - 1)) {
            ans = len;
            break outer;
        }
    }
}

주어진 문자의 길이에서부터 하나씩 줄여가며 탐색합니다.
이 때 팰린드롬이면 바로 루프를 빠져나가면 됩니다.

3. 전체 코드

function solution(s) {
    const N = s.length;
    const memo = [...Array(N)].map(() => [...Array(N)].map(() => -1));
    let ans;

    const isPal = (a, b) => {
        // 길이가 1일 때
        if (a == b) return 1;

        // 길이가 2일 때
        if (a + 1 == b) return s[a] == s[b] ? 1 : 0;

        if (memo[a][b] != -1) return memo[a][b];

        // s[a] == s[b] 라면, 재귀적으로 안에있는 문자열도 팰린드롬인지 확인
        return memo[a][b] = s[a] == s[b] ? isPal(a + 1, b - 1) : 0;
    };

    outer:
    for (let len = N; len >= 1; len--) {
        for (let a = 0; a <= N - len; a++) {
            if (isPal(a, a + len - 1)) {
                ans = len;
                break outer;
            }
        }
    }

    return ans;
}