[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합니다.

 

 

나의 풀이

 문제가 되게 간결하길래 쉬운 줄 알았는데, 난이도가 꽤 있었다. 그래서 바로 다른 사람의 코드를 봤다. 엄청나게 기발한 코드 였다. 따라서, 두 번째 예시로 나의 풀이를 풀어보려고 한다.

 

[그림 1] 두 번째 예시 문자열

 

 두 번째 예시의 문자열 길이는 6이다. 먼저, 문자열이 팰린드롬인지 아닌지 판별하는 과정부터 볼 것이다. 과정은 다음과 같다.

 

 

 먼저, 문자열의 가운데 인덱스를 구한다. 공식은 문자열의 길이/2다. 위 예시로 첫 가운데 인덱스는 3이된다. 그 다음에는 첫 번째와 끝 문자 일치여부를 검사하고, 두 번째는 양쪽에서 한 칸이동 후에 두 번째 문자와 끝에서 두 번째 문자의 일치여부를 검사한다. 한 번이라도 일치하지 않는다면, 그 문자열은 팰리드롬이 아니다.

 

 

 팰리드롬은 위와 같은 방식으로 판별하면 된다. 그 외에 다른 작업을 해줘야 한다. 그 작업은 문자열을 길이별로 자르는 작업이다. "abacde"의 길이는 6이다. 만약 "abacde"가 팰리드롬이면, 정답은 6이 된다. 하지만 "abacde"는 팰리드롬이 아니기 때문에, "abacde"의 길이를 5로 만들어서 팰리드롬 여부를 판단해야한다. 경우의 수는 다음과 같다.

 

 

 "abcde"의 길이를 5인 문자열로 자르면, "abacd", "bacde"가 나온다. 그리고 두 문자열을 팰리드롬인지 아닌지를 판별한다. 만약 두 문자 중에 하나라도 팰리드롬이라면, 문자열의 길이를 바로 반환하면 된다. 이런 방식으로 제일 긴 팰리드롬이 나올 때까지 길이를 1씩 차감하면 된다.

 

 

정리하면 다음과 같다.

1. 문자열의 길이를 1씩 차감한다.

2. 차감한 각각의 문자열을 팰리드롬인지 아닌지를 판별한다.

3. 만약 팰리드롬일 경우 바로 길이를 리턴한다.

const solution = (s) => {
  for(let i=s.length; i>=1; i--){
    for(let j=0; j<=s.length-i; j++){
      const isPalin = isPalindrome(s.slice(j, i+j));
      if(isPalin) return i;
    }
  }
  return 1;
}

const isPalindrome = (s) => {
  const half = Math.floor(s.length/2);

  for(let i=0; i<half; i++){
    if(s[i] !== s[s.length-1-i]) return false;
  }

  return true;
}