[js문제풀이] 가장 긴 팰린드롬

문제

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

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

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

---

입출력 예

s answer

"abcdcba"	7
"abacde"	3

입출력 예 설명

입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2
2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.

접근 및 풀이

문자열의 크기가 크지 않아서 별다른 방법 없이 전수 조사를 했다. 다만, slice와 sort를 이용하면 효율성에서 막혀서 인덱스 단위로 비교해야했다. 가장 큰 가능성의 크기부터 두 개의 포인터로 같은것을 비교해 전부 통과한다면 길이를 반환하게끔 for문을 만들었다. 앞뒤의 범위가 안겹치는 경우와 하나만 겹치는 경우 두가지 모두를 찾기 위해 두가지 경우로 나눠야 했다. 두 경우를 현재 len에서 같은 loop문으로 돌리면 문제가 생긴다. "abacca"에서 len이 2일 때 ab____와 __ac__를 비교하고 _ba____, ___cc_로 넘어가야 하는데 같은 loop문이라면 해당 비교 후 ab____와 _ba___를 비교해 뒤에 있는 더 긴 가능성을 보지 못하고 종료하게된다. 따라서 두 경우를 분리해서 범위가 안 겹치는 경우를 먼저 모두 탐색한 뒤에 하나가 겹치는 경우를 탐색해야한다.

코드

function solution(s) {
  for (let len = Math.ceil((s.length / 2)); len > 0; len -= 1) {
    for (let leftStart = 0; leftStart + (len * 2) - 1 < s.length; leftStart++){
      let rightStart = leftStart + (len * 2) - 1;
      let [li,ri] = [leftStart, rightStart];
      for (li = leftStart, ri = rightStart; s[li] === s[ri] && li <= ri; li++, ri--);
      if (li > ri) return len * 2;
    }
    for (let leftStart = 0; leftStart + (len * 2) - 2 < s.length; leftStart++){
      let rightStart = leftStart + (len * 2) - 2;
      let [li,ri] = [leftStart, rightStart];
      for (li = leftStart, ri = rightStart; s[li] === s[ri] && li <= ri; li++, ri--);
      if (li > ri) return len * 2 - 1;
    }
  }
  return 1;
}

출처

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