[프로그래머스] 가장 긴 팰린드롬

문제 설명

어떤 문자열을 뒤집어도 같다면 그 문자열을 팰린드롬이라고 한다.
이 문제에서는 문자열이 주어지면 부분 문자열 중에서 가장 긴 팰린드롬을 찾고 그 길이를 출력하는 문제였다.

처음엔 모든 부분 문자열을 구한 다음에 split, reverse 등의 배열 메소드를 사용해서 팰린드롬인지 확인하고 그 길이를 저장하는 식으로 접근했었다.

기본 테스트 케이스는 다 통과했지만, 정확성 테스트에서 실패했다.

처음 작성했전 코드

function solution(s) {
  let answer = Number.MIN_SAFE_INTEGER;

  if (s.length === 1) {
    return 1;
  }

  if (s.length === 2 && s[0] === s[1]) {
    return 2;
  }
  const arr = Array.from({ length: s.length + 1 }, (_, i) => i);
  const comb = [];
  const visit = Array(s.length).fill(false);
  const dfs = (depth, start, path) => {
    if (depth === 2) {
      comb.push(path);
      return;
    }
    for (let i = start; i < arr.length; i++) {
      if (!visit[i]) {
        visit[i] = true;
        dfs(depth + 1, i + 1, path + String(arr[i]));
        visit[i] = false;
      }
    }
  };
  dfs(0, 0, "");

  const subString = comb.map((v) => {
    const [from, to] = v.split("");
    const string = s.slice(from, to);
    return string;
  });

  subString.forEach((v) => {
    const reverse = v.split("").reverse().join("");
    if (v === reverse) {
      answer = Math.max(answer, v.length);
    }
  });

  return answer;
}

사실 아직도 어느 부분에서 정확성 테스트가 실패했는지 알지 못하겠다.
효율성이 좋지 않아서 나중에 다시 이 방법으로 시도해볼 가능성은 없지만 이유가 궁금하다...ㅎㅎ

정답으로 제출한 코드

function solution(s) {
    let answer = 1
    for (let i = 0; i < s.length; i++) {
        let start = i
        let end = i
        while(start >= 0 && end < s.length && s[start] === s[end]) {
            start--
            end++
        }
        answer = Math.max(answer, end - start - 1)
    }
    for (let i = 0; i < s.length; i++) {
        let start = i
        let end = i + 1
        while(start >= 0 && end < s.length && s[start] === s[end]) {
            start--
            end++
        }
        answer = Math.max(answer, end - start - 1)
    }
    return answer
}

이 문제의 풀이 방법은 특정 인덱스를 기준으로 양쪽으로 확장해나가면서 팰린드롬인지 확인하는 방법이다.
확장해나갈 때 주의할 것은 문자열의 인덱스 범위를 지켜야 한다는 점과 홀수와 짝수인 경우를 구분해서 풀이를 해야한다는 점이다.

먼저 홀수인 경우에는 start와 end가 가리키는 문자열이 같은 상태로 양쪽으로 확장해나가고, 짝수인 경우에는 start의 바로 오른쪽에 end를 초기화해서 양쪽으로 확장해나가면서 양쪽 끝의 문자열이 같은지 확인하는 방법이다.

그렇게 반복적으로 문자열의 양쪽 끝이 같은지 확인하고 그 길이가 가장 긴 경우를 저장해서 출력하면 끝이다.

출처
유튜버 달레의코드님의 영상
https://www.youtube.com/watch?v=rGySPuTuYEI
프로그래머스 - 가장 긴 팰린드롬
https://school.programmers.co.kr/learn/courses/30/lessons/12904