[Algorithm] 가장 긴 팰린드롬

📋 문제 

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

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

 

제한사항

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

 

입출력 예

"abcdcba"	7
"abacde"	3

 

✏️ 풀이

어떤 식으로 풀어야할지 정말 고민을 많이 했다. 처음 선택한 방법은 이중 for문을 돌려서 알파벳이 같은지 이차원 배열에 표시하고 i는 작아지는 방향으로, j는 커지는 방향으로 반복문을 돌리면서 체크하며 더해가는 방법으로 접근했다. 하지만 이런 방식을 선택했을 때 'aacbaa'처럼 가운데 문자는 팰린드롬의 조건을 충족시키지 못하지만 사이드의 aa가 팰린드롬으로 계산되어 4라는 답이 도출됬다.

 

다음으로는 i는 작아지는 방향으로, j는 커지는 방향으로 이중 for문을 한번만 돌리면서 i, j인덱스가 같다면 1을 할당하고 i, j의 인덱스 차이가 1일때 같다면 2를 할당, 만약 i+1, j-1에 값이 있다면 check[i+1][j-1]의 값에 2를 더해서 할당했다. check[i+1][j-1]의 값을 확인하는 이유는 이차원 배열에 표시할때 i는 큰값에서 작은 값으로, j는 작은 값에서 큰 값으로 도는데 값이 있다면 더 작은 단위의 팰린드롬이 있다는 의미이기 때문이다.  i+1, j-1를 확인할 때 현재 i, j의 인덱스에 해당하는 값이 같다면 그 작은 단위의 팰린드롬의 양 사이드가 값음을 의미한다.

 

⌨️ 코드

function solution(s) {
  var answer = 0;

  const len = s.length;
  const check = [...Array(len)].map(_ => new Array(len).fill(0));

  for (let i = len; i >= 0; i--) {
    for (let j = i; j < len; j++) {
      if (i === j) check[i][j] = 1;
      else if (s[i] === s[j]) {
        if (i + 1 < len && j - 1 >= 0 && check[i + 1][j - 1]) {
          check[i][j] += check[i + 1][j - 1] + 2;
        } else if (j - i === 1) {
          check[i][j] = 2;
        }
      }

      answer = answer = Math.max(answer, check[i][j]);
    }
  }

  return answer;
}