(javascript) 프로그래머스 가장 긴 팰린드롬

[문제링크]

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

[문제]

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

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

제한사항

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

[풀이]

level3 도전하다가 첫번째로 막힌 문제입니다. 문제를 처음에 보았을 때, 문제 유형을 판단하기 어려웠습니다. 차근차근 시뮬레이션 돌려보자는 마음으로 2중 for문을 이용하여 모든 단어를 조사하였고, 기본 테스트 케이스는 통과하였습니다. 하지만 이 후의 채점에서 몇개의 테스트케이스와 효율성체크에서 실패하였습니다.

• 첫번째 코드
  첫번째 코드에서는 2중 for문을 이용하여 "abcd" 라는 단어가 주어진다면 "abcd" "abc" "bca" "ab" ... 순으로 검사하였습니다.
  여기서 몇개의 테스트가 실패한 이유는 검사시에 s.includes(r) (여기서 r은 reverse된 sentence)로 검사했기 때문입니다.
  s는 원본 sentence 이기 때문에 s.includes(r)을 한다면 "abcDFGcba" 와 같은 단어를 보았을때, "abcDFGcba".includes("cba")에 true를 반환하여 팰린드롬이 아닌 단어를 인식합니다.
  includes를 사용하기 위해선 s.includes가 아닌 s.slice(i, s.length-t+i).includes를 사용해야합니다.

function solution(s) // 실패한코드
{
    var answer = 0;
    var min=-1
    for(var t=0; t<s.length ; t++ ){
        for(var i=0;i<=t; i++){
            if(min!=-1){ break }
            var r=s.slice(i,s.length-t+i).split("").reverse().join("");
            if(s.includes(r)) { //테스트케이스 실패 원인 
                min=t
                break
            }
        }
    }
    answer= s.length-min
    return answer;
}

이후에는 효율성 부분에서 막히게 되었습니다. 효율성 부분을 해결하기 위해서는 s.includes(r)로 전체를 비교하는 것이아닌 for문을 통해 하나하나 비교하는 것이 $Big-O$일 때, 효율성 측면에서 좋습니다.
함수가 더 스파게티코드가 되는 것을 방지하여 $is$_$palindrom()$ 함수를 따로 정의하여 가독성을 조금 더 높혔습니다.

[성공 코드]

function solution(s) {
  var len = s.length
  var answer = -1
  for (var i = 0; i < len; i++) {
    if (answer > -1) break
    for (var t = 0; t <= i; t++) {
      if (s[t]===s[len-i+t-1]&&is_palindrome(s.slice(t, len - i + t))) {
        answer = len - i
        break
      }
    }
  }

  return answer;
}
function is_palindrome(s) {
  var chk = true
  for (var i = 1; i < s.length; i++) {
    if (s[i] != s[s.length - 1 - i]) {
      chk = false
      break
    }
  }
  return chk
}

이 방식으로 효율성을 해결하였습니다.