[Programmers] 가장 긴 팰린드롬

코딩테스트 연습 - 가장 긴 팰린드롬

---

  팰린드롬은 앞뒤를 뒤집어도 똑같은, 예를 들어 '토마토' 같은 문자열이다. 문자열을 주면 가장 긴 팰린드롬을 찾는 문제이다.

 

1. 문제 분석

길이 1인 회문

  문제의 핵심은 어떤 문자열이 회문임을 알면 해당 문자열의 앞뒤 글자만 확인하면 더 긴 회문이 있는지 확인할 수 있다는 점이다. 예를 들어 위처럼 'abcba' 문자열에서 길이 1인 회문 'c'를 찾았다고 해보자. 이 때 c 앞뒤의 문자열을 보면 더 긴 회문이 존재하는지 확인할 수 있다.

 

길이 3인 회문

  찾은 길이 3인 회문에서 다시 앞뒤 글자를 보면 모두 a이다. 따라서 'abcba'의 가장 긴 회문은 'abcba'이다.

 

길이 2인 회문

  회문이 짝수라면 어떨까? 짝수인 경우에는 길이 2인 회문이 있다면 회문의 앞뒤를 비교하여 4인 회문을 찾아나갈 수 있다. 예를 들어 위와 같이 'abccbc'문자열에서 길이 2인 회문 'cc'를 찾아냈다면 해당 회문의 앞뒤 글자가 같은지 확인하여 길이 4인 회문 'bccb'를 쉽게 발견할 수 있다.

 

회문 기록

  위 사실들을 조합하면, 가장 긴 회문을 찾기 위해서는 먼저 길이 1인 회문과 2인 회문을 찾아야 한다. 길이 3이상인 회문을 찾기 위해서는 지금까지 찾은 회문에서 앞뒤 한 칸씩을 비교한다. 이를 위해선 찾은 회문들을 저장하는 공간이 필요할 것이다. 또한 회문은 작은 길이부터 큰 길이 순으로 찾아나가야 할 것이다.

 

  예를 들어 abcba에서 bcb 회문을 찾은 상태의 기록은 위 그림과 같다. 먼저 길이 1, 2인 회문에 모두 True를 넣는다. 이 경우는 길이 2인 회문이 없었다. 그 후 길이 3인 회문 bcb를 기록한다. 시작이 b(index=1)이고 끝이 b(index=3)인 회문이다.

 

  위 그림에서 길이 5인 회문을 찾아보자. 확인해야 하는 회문은 start 인덱스가 0이고, end 인덱스가 4이다. 첫 번째로 이 둘의 값은 'a'로 동일하다. 다음으로 이 회문의 내부인 'bcb'가 회문인지 확인한다. 이는 표로 확인할 수 있다. array[start+1][end-1] 이 true라면 회문이기 때문이다!

 

 

2. 코드

function solution(s) {
  // 문자열이 1글자라면 바로 리턴
  if (s.length < 2) return s.length;

  // 현재까지 찾는 회문의 최대길이
  let max = 1;
  // 찾은 회문 기록하기
  const isPalindrome = [...Array(s.length)].map(() => Array(s.length).fill(false));

  // 1. 길이 1인회문 찾기
  for (let i = 0; i < s.length; i++) {
    isPalindrome[i][i] = true;
  }

  // 2. 길이 2인 회문 찾기
  for (let i = 0; i < s.length - 1; i++) {
    if (s[i] === s[i + 1]) {
      isPalindrome[i][i + 1] = true;
      max = 2;
    }
  }

  // 3. 길이 3
  for (let cnt = 3; cnt <= s.length; cnt++) {
    for (let start = 0; start <= s.length - cnt; start++) {
      const end = start + cnt - 1;
      if (isPalindrome[start + 1][end - 1] === true && s[start] === s[end]) {
        isPalindrome[start][end] = true;
        max = cnt;
      }
    }
  }

  return max;
}