[알고리즘] 프로그래머스 - 가장 긴 펠린드롬

https://programmers.co.kr/learn/courses/30/lessons/12904

문제설명

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

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

---

만약 주어진 문자열이 펠린드롬인지 아닌지 찾는 방법은 간단하다.
만약 문자열 s가 펠린드롬인지 확인하기 위해서는

if(s === s.split("").reverse().join(""))

이 조건문으로 확인할 수 있다.

그런데 이 문제는 s의 부분 문자열 중 가장 긴 펠린드롬을 찾아야 한다!

그럼 생각해야 할 것이 2가지 이다.
첫번째로는 주어진 문자열이 펠린드롬인지 찾는 함수가 있어야하고,
두번째로는 주어진 문자열의 모든 부분 문자열을 구해야 한다.

그래서
펠린드롬을 찾는 함수를

function isPal(str) {
    if(str.length < 2) return true;
    return str === str.split("").reverse().join("") ;
}

이렇게 구성하고

주어진 문자열에 대해 부분문자열을 구하는 방식을 아래와 같이 구성할 수 있다.

function solution(s) {
    for(let i = s.length; i > 1; i--) {
        for(let j = 0; j < s.length - i + 1; j++) {
            if(isPal(s.substr(j, i))){ return i;}
        }
    }
    return 1;
}

위의 코드가 작동하는 방식을 손으로 적어봤다!
for문과 substr()메서드를 사용해서 모든 부분 문자열을 구할 수 있다!

그런데 이렇게 작성하고 코드를 돌려보니 정확성에서는 통과가 되는데 효율성에서 통과가 안된다..

효율성 문제까지 해결을 하기 위해서는 isPal 함수를 아래와 같이 구성해야 한다.

function isPal(str) {
    if(str.length < 2) return true;
    if(str.slice(0, 1) === str.slice(-1)){
        return isPal(str.slice(1, -1));
    } else {
        return false;
    }
}

재귀호출을 통해 바깥에서부터 한글자씩 비교를 하면서 팰린드롬인지 아닌지 확인할 수 있다!

---

이 문제는....너무어렵다

같이 공부하시는 분이 도움을 주셔서 이해할 수 있었다.

앞으로 열심히 알고리즘을 공부해야겠다...