[JS] 가장 긴 팰린드롬 - dp를 잘 써보자!

레벨 3도 앞장을 다 했네요.앞장에서는 우선순위 큐(힙)나 덱과 같은 자료구조나 최소거리 문제, 완전 탐색 같은 주제였는데요.다시 dp를 다뤄볼 때가 온 것 같습니다. 이게 가장 어려운 것 같아요.

 

같이 한 번 볼까요?

---

문제 요약

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

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

 

제한사항

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

테스트케이스

s	answer
"abcdcba"	7
"abacde"	3

 

접근 방법

다양한 접근 방법이 있겠습니다만..

팰린드롬에서 기본적으로 모든 문자를 순회하는 방법은 보통 효율성 테스트에서 걸리게 되어있습니다.

 

이 문제에선 2번 테케가 걸리네요.

 

dp를 이용해서 걸러줘야하는데요.

일반적으로 이 문자 s가 회문인지 검사하는 방법은 아래와 같습니다.

 

(start = 0, end = n - 1) 양 끝 문자가 같은지 비교한다.
(start = 1, end = n - 2) 그 다음 문자가 같은지 비교한다.
...
(start = x, end = x || x + 1) 가장 중간 문자가 같은지 비교한다.

 

어떤 길이가 최대 길이인지 모르는 상황에서 같은 비교를 몇 번씩이나 해야하는 상황입니다.

이러면, 길이를 기준으로 순회를 하면서, dp를 만들어주면 적은 연산으로 비교가 가능합니다.

 

dp[start][end] 이렇게 만든 뒤, start와 end가 같은 글자라면 true로 채워줍시다.

이렇게 하면 매번 회문 비교를 위한 루프는 생략할 수 있습니다.

 

(start = 0, end = n - 1) 양 끝 문자가 같은지 비교한다.
dp[start + 1][end - 1]이 true인지 확인한다.

 

이렇게 훨씬 적은 연산으로 처리할 수 있겠군요.

 

정답 코드

function solution(s) {
    const n = s.length;
    const memo = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => i === j));
    let answer = 1;
    
    for(let i = 0; i < n - 1; i++) {
        if(s[i] === s[i+1]) {
            memo[i][i+1] = true;
            answer = 2;
        }
  }
    
    for (let length = 2; length <= n; length++) {
        for (let start = 0; start <= n - length; start++) {
            const end = start + length - 1;
            if (s[start] === s[end] && memo[start + 1][end - 1]) {
                memo[start][end] = true
                answer = length;
            }
        }
    }
    
    return answer;
}

실행 결과

 

팁 1. 왜 길이 2는 따로 계산하나요?

// length: 2 인 경우,
memo[i][i + 1]

// length > 2 인 경우,
memo[start + 1][end - 1]

 

2 이상인 경우에는 index를 1씩줄여가면서 계산이 되는데,

2인 경우만 다릅니다. 그러니, 2일 때는 따로 계산해줘야합니다.

 

팁 2. memo가 의미하는 건 뭔가요?

memo[start][end]

// start === end 라면 길이가 최소 1입니다.
// start === start + 1 이라면 길이가 최소 2입니다.

 

start부터 end까지 팰린드롬이라면 true를 넣어줍니다.

초기 세팅으로 길이가 2인 경우까지 직접 초기화를 시켜주고 밑에 루프를 돌면서 갱신해줍니다.

dp 문제는 풀고 나면 별거 없는 것 같은데, 항상 어떻게 자료를 정리해야할까를 오래 고민하게 되네요.

익숙해질때 까지 반복해야겠습니다.

 

그럼 이만!