[프로그래머스] LV.3 가장 긴 팰린드롬 (JS)

문제

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

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

제한

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

입출력 예시

s	answer
"abcdcba"	7
"abacde"	3

풀이

팰린드롬을 찾는 가장 간단한 방법은 앞 글자부터 하나씩 늘려가며 마지막 글자까지 비교하며 해당 범위가 팰린드롬인지 검사하면 될 것 이다. 하지만 이 경우는 O(N^3)의 시간복잡도가 걸리고 주어진 문자열 s의 길이가 최대 2500이기 때문에 효율성을 통과할 수 없을 것이다. 따라서 완전탐색 말고 다른 효율적인 방식을 선택해야 할 것이다.

위 과정을 먼저 몇 개만 순서대로 나열해보자. 입출력 예시의 두 번째인 abacde가 입력 문자열이라고 가정한다. 그렇다면 위의 방법대로면 다음의 과정으로 팰린드롬을 찾게 될 것이다.

1. 시작문자 a ~ 종료문자 b

   • 양 끝이 서로 일치 X => 팰린드롬 X
   • 따라서 종료문자의 다음 글자를 탐색

2. 시작문자 a ~ 종료문자 a

   • 양 끝이 서로 일치 O => 팰린드롬 조건 충족
   • 가운데 있는 문자열도 팰린드롬인가?
   • 문자 b만 있기때문에 팰린드롬 O
   • 더 긴 길이의 팰린드롬이 있을 수 있으므로 계속 다음 문자 탐색

3. 시작문자 a ~ 종료문자 c

   • 양 끝이 서로 일치 X => 팰린드롬 X
   • 따라서 종료문자 다음 글자를 탐색

4. 시작문자 a ~ 종료문자 d

   • 양 끝이 서로 일치 X => 팰린드롬 X
   • 따라서 종료문자 다음 글자를 탐색

5. 시작문자 a ~ 종료문자 e

   • 양 끝이 서로 일치 X => 팰린드롬 X
   • 따라서 종료문자 다음 글자를 탐색

이때 찾은 팰린드롬이 최대길이라는 것을 보장할 수 없기 때문에 위의 과정을 각 문자들에 하나씩 모두 실행해야 한다.

그런데 여기서 2번의 굵은 글씨부분에서 일련의 연산이 중복되어 불필요한 계산이 발생할 것을 파악할 수 있어야 한다. 이를 파악할 수 있다면 우리는 해당 문제를 어떻게 접근할 지에 대한 실마리를 얻을 수 있다.

그렇다면 어디서 불필요한 연산이 중복 발생하는지 살펴보자. 먼저 팰린드롬이 되기 위해서는 다음의 조건을 충족해야 한다.

1. 양 끝의 문자가 서로 일치한다.
2. 양 끝의 문자 사이에 있는 문자열의 길이가 0 또는 1 이거나
3. 양 끝의 문자 사이에 있는 문자열 역시 팰린드롬이어야 한다.

여기서 3번의 조건이 문제다. 우리는 팰린드롬을 찾기 위해 반복문을 돌리고 있는데, 그 내부에서 또 다시 팰린드롬인지 아닌지를 따로 검사를 돌려야하는 것이다. 즉 무언가 불필요한 연산이 발생할 거 같다는 느낌적인 느낌은 든다. 위의 예시를 통해 좀 더 딥하게 들어가보자.

이번엔 시작문자가 두 번째 문자인 b 라고 가정하고 위의 과정을 반복한다고 생각해보자. 그렇다면 다음의 과정이 요구될 것 이다.

1. b - a : 팰린드롬 X
2. b - c : 팰린드롬 X
3. b - d : 팰린드롬 X
4. b - e : 팰린드롬 X

그런데 위에서 4번의 과정과 시작문자가 a일때의 5번의 과정을 잠깐 같이 보자. 만약 5번의 과정에서 a - e 범위에서 내부 문자열이 팰린드롬인지 아닌지를 검사했다고 가정해보자 (실제로는 양 끝 문자가 달라 검사하지는 않았다). 그렇다면 시작문자가 b일때 4번의 과정은 내부 문자열이 팰린드롬인지 새로 검사할 필요 없이 이전에 검사해놓은 결과를 이용해서 판단할 수 있을 것이다. 즉 이전의 결과를 활용해서 현재 검색에 이용할 수 있는가? 라는 조건을 충족한다. 이 조건을 충족한다면 우리는 해당 문제를 DP(Dynamic Programming)을 이용해 풀이할 수 있다.

DP를 적용할 수 있다는 것을 파악하는 것도 어렵지만, 그 다음으로 또 어렵고도 가장 중요한 것이 DP 배열을 어떻게 초기화할 것인가와 점화식이 무엇인지 찾아내는 것이다. 먼저 DP 배열 초기화를 살펴보자. 우리는 각 문자열이 팰린드롬임을 검사함과 동시에 그 문자열의 범위가 팰린드롬인지 아닌지를 DP에 저장할 것이다. 때문에 다음과 같은 정의를 내릴 수 있다.

• DP[i][j] = true : 시작문자 i 부터 종료문자 j 까지의 문자열이 팰린드롬이라면 true, 아니면 false

위와 같이 2차원 배열로 선언한다면 우리는 어디서 시작하고 어디서 종료하는지에 따른 모든 문자열의 범위에 대해 팰린드롬 여부를 저장할 수 있다. 따라서 DP 배열의 초기화는 다음과 같이 2차원 배열로 이루어져야 한다.

const len = s.length;
// 주어진 s의 길이크기의 2차원 배열 생성
// int dp[][] = new int[len][len] 과 동일
const dp = new Array(len).fill().map(_ => new Array(len).fill(false));

그리고 해당 배열의 초기화는 두 번에 걸쳐 생각할 수 있다. 먼저 모든 dp[i][i]는 항상 true 이다. 이를 해석하면 시작문자i 부터 종료문자i 까지의 범위이므로 이는 곧 자기 자신을 뜻하며, 나 자신 하나의 경우는 항상 팰린드롬이 성립한다. 또한 길이가 2인 팰린드롬의 여부도 원한다면 초기화가 가능하다. 이때는 현재문자 i 와 바로 뒤에 위치한 i+1이 서로 같은지만 체크해주면 되기 때문이다. 따라서 초기화는 다음과 같이 진행할 수 있다.

let answer = 1;  // 가장 긴 팰린드롬의 길이를 저장할 변수 (문자열은 최소 1의 길이를 가지므로 default를 1로 초기화)

// 자기자신은 곧 팰린드롬이다
for(let i = 0; i < len; i++) {
  dp[i][i] = true;
}

// 길이가 2인 팰린드롬이 있는지 검사한다
// 판단조건은 s[i] == s[i+1]이 일치하면 
// 길이가 2인 팰린드롬이 성립한다.
// 성립할 경우 answer도 2로 갱신한다.
// dp[i][i+1]의 범위를 탐색하므로
// 반복문을 0부터 len-1 까지 하는것에 주의하자.
for(let i = 0; i < len - 1; i++) {
  if(s[i] === s[i+1]) {
    answer = 2;
    dp[i][i+1] = true;
  }
}

위의 과정이 끝나면 DP 배열은 성공적으로 초기화를 마칠 것이다. 이제 점화식을 적용하여 문제의 답을 찾아보자. 우리는 앞서서 길이가 2인 팰린드롬이 있는지 없는지도 초기화에서 같이 진행했기 때문에, 점화식은 길이가 3인 팰린드롬을 검사하는 것부터 진행할 수 있을 것이다.

다시 앞에 팰린드롬 충족 조건의 3번을 생각해보자. 시작문자와 종료문자가 일치했다면, 내부 문자열 역시 팰린드롬이어야 한다. 위에서 우리는 DP 배열을 통해 내부문자열의 범위를 계산할 수 있다. 다음을 살펴보자.

• 시작문자가 start 이고 종료문자가 end 일때
• 첫번째 조건: s[start] === s[end] 로 나태낼 수 있다.
• 세번째 조건: dp[start+1][end-1] 로 나타낼 수 있다.

따라서 위의 두가지 조건이 모두 충족된다면 dp[start][end] 역시 팰린드롬이 성립하는 것을 알 수 있다. 이는 우리가 초기화에서 길이가 2인 팰린드롬의 범위를 모두 지정했기 때문에, 이 값을 이용해서 다음 길이인 3, 4, 5.... 역시 계속 이전 결과를 활용해서 현재 결과를 구할 수 있는 것이다. 이때 start 인덱스 값에 주의하며 이를 구현한 코드를 살펴보자.

// 길이가 3인 팰린드롬이 있는지 검사할 것이다
// 최대 팰린드롬 길이는 주어진 문자열과 동일할 수 있기에(예제1번)
// len과 일치할 때 까지 반복문을 돌린다는 것을 주의하자
for(let i = 3; i <= len; i++) {
  // 시작문자는 항상 0부터 시작할 것이다.
  // 시작문자가 가질 수 있는 최대 index값은 len - i와 같다.
  // 이는 현재 팰린드롬의 길이가 i인 상황이기 때문에
  // 이 길이보다 짧아지는 index는 필요없기 때문이다.
  for(let start = 0; start <= len-i; start++) {
    // 종료문자의 index는 시작문자 index + 현재 팰린드롬 길이 i - 1 이다.
    // 즉 i 크기만큼 떨어져있는 곳의 index이다.
    const end = start + i - 1;
    if(s[start] === s[end] && dp[start+1][end-1]) {
      dp[start][end] = true;
      // answer 의 값은 항상 최대값으로 갱신되어야 한다.
      answer = Math.max(answer, i);
    }
  }
}
    

따라서 최대 O(N^2)의 시간복잡도가 최대 N의 크기가 2500이기 때문에 효율성 테스트 역시 무난하게 통과할 수 있다. 주석을 제외한 전체 코드는 다음과 같다.

코드

function solution(s) {
  let answer = 1;
  const len = s.length;
  const dp = new Array(len).fill().map(_ => new Array(len).fill(false));
  
  for(let i = 0; i < len; i++) {
    dp[i][i] = true;
  }
  
  for(let i = 0; i < len - 1; i++) {
    if(s[i] === s[i+1]) {
      dp[i][i+1] = true;
      answer = 2;
    }
  }
  
  for(let i = 3; i <= len; i++) {
    for(let start = 0; start <= len - i; start++) {
      const end = start + i - 1;
      if(s[start] === s[end] && dp[start+1][end-1]) {
        dp[start][end] = true;
        answer = Math.max(answer, i);
      }
    }
  }
  
  return answer;
}

출처

https://programmers.co.kr/learn/courses/30/lessons/12904#