[JS] 가장 긴 팰린드롬

문제

프로그래머스

 

풀이

이번 문제는 투 포인터 알고리즘 처럼 풀이할 수 있지만(링크), DP 알고리즘을 이용해 풀이했다.

 

우선 DP의 구조는 시작 지점과 끝 지점의 위치를 이용했다.

DP[시작][끝] 이런 구조를 갖고 있으며, 이러한 구조는 시작 위치의 문자와 끝 위치의 문자가 일치하는지 true false로 구분해 저장한다.

 

코드

const solution = (s) => {
  let answer = 1;
  const dp = Array.from({ length: s.length }, (_, i) => Array.from({ length: s.length }, (_, j) => i === j));

  for (let i = 0; i < s.length - 1; i++) {
    if (s[i] === s[i + 1]) {
      dp[i][i + 1] = true;
      answer = 2;
    }
  }

  for (let i = 3; i <= s.length; i++) {
    for (let st = 0; st <= s.length - i; st++) {
      const end = st + i - 1;
      if (s[st] === s[end] && dp[st + 1][end - 1]) {
        dp[st][end] = true;
        answer = i;
      }
    }
  }

  return answer;
}