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

문제

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

function solution(s){
    const max = s.length
    const isPalin = (str) => {
        const half = Math.floor(str.length/2)
        for(let i=0;i<half;i++){
            const left = str[i]
            const right = str[str.length-1-i]
            if(left !== right){
                return false
            }
        }
        return true
    }
    for(let i=max;i>=1;i--){
        for(let j=0;j<max-i;j++){
            if(isPalin(s.slice(j,i+j+1))){
                return i+1
            }
        }
    }
        return 1
}

풀이

사실 펠린드롬 판단하는건 그리 생각해내기 어렵지 않은듯**

- 반복문으로 index 0에서 끝까지 도는데 하나는 왼쪽에서부터 비교 / 하나는 오른쪽에서부터 비교해서 하나라도 틀리면 팰린드롬 아님

- 근데 문자열 길이 반을 넘어가면 뭔가 비교했던걸 또 비교하는 느낌

=> 문자열 길이의 반값을 구해서 거기까지만 왼쪽 - 오른쪽 비교해보면 된다는 걸 알 수 있음

문제는... 효율성에서 통과를 계속 못하길래 처음에는 문자열 한개일때는 무시하게도 해보고 했는데도 계속 안됨

=> 애초에 이 문제는 길이의 최댓값을 구하는 문제임 = 길이가 제일 긴 것부터 비교하는 게 제일 효율적이라는 소리

(저 이중for문이 제일 어려웠음...)

아직도 완벽하게 이해한건 아니지만...

 i = 내가 구하고 싶은 문자열의 길이 - 긴거부터 구하는 게 효율적이니깐 length부터 --
 j = 문자열의 시작점 - j+i가 문자열의 length보다 클 수 없다는 걸 이용해서 j는 length - i까지 ++

 그러면 이제 slice를 이용해서 문자열을 잘라주면 되는데 , 일단 시작점은 j니깐 (j,x)로 놓고 
 끝을 생각해보면 j가 아닌 j+i로 둬야하는데, 이렇게 해야 계속해서 시작점과 끝점이 달라지면서 주어진 문자열에서 
 원하는 부분문자열을 모두 구할 수 있음

이렇게 하면 'ababc' 라는 문자열이 있으면 'ababc' -> 'abab -> 'babc' -> 'aba' .... -> 2개 -> 1개까지 부분문자열을 구해줌

최댓값부터 먼저 구하기 때문에 발견되면 바로 return - 없으면 1이 정답이 됨(a b 이런건 무조건 펠린드롬이니깐)

• 재귀버전

const dfs = (n) => {
  if (n === 0) {
    return;
  }
  for (let i = 0; i <= str.length - n; i++) {
    console.log(i, n + i);
  }
  dfs(n - 1);
};

dfs(str.length);