문제 설명
앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.
예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.
제한사항
문자열 s의 길이 : 2,500 이하의 자연수
문자열 s는 알파벳 소문자로만 구성
입출력 예
| s | answer |
|---|---|
| "abcdcba" | 7 |
| "abacde" | 3 |
입출력 예 설명
입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.
입출력 예 #2
2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.
처음엔 문자열의 중심이되는 인덱스값을 기준으로 해당 인덱스 문자열 양쪽을 비교해나가는 반복문을 사용해서 팰린드롬을 찾고, 중심 인덱스를 이동시켜 다시 반복하는 방식으로 풀어보려고했다. 하지만 이 경우엔 1,3,5,7.. 처럼 홀수개의 팰린드롬만 찾을 수 있다.
그럼 홀수인 팰린드롬을 찾아주고 나서 짝수인 팰린드롬도 찾아준다면?
블로그를 정리하다가 갑자기 위의 질문에 대한 답이 생각이 나서 DP를 사용하지않고 풀어버렸다.
function solution(s){
// 아래 함수는 s의 길이가 2이상 일때부터 검사가 되기때문에 result에 기본값으로 1을 넣어준다
// 1길이의 문자열은 자기자신만으로 팰린드롬이기 때문에
const len = s.length;
const result = [1];
for(let i = 1; i < len-1; i++){
let oddPalinLen = 1;
let evenPalinLen = 0;
for(let j = 1; j <= i; j++){
if(s[i-j] === s[i+j]) oddPalinLen += 2;
else break;
}
for(let j = 1; j <= i; j++){
if(s[i-j] === s[i+j-1]) evenPalinLen += 2;
else break;
}
result.push(oddPalinLen, evenPalinLen);
}
return Math.max(...result)
}
// 통과해버려따.. 그럼 이어서 DP를 이용하는 방법에 대해 알아보자.
팰린드롬인지 검사하는 방법
"abcddcbe"를 작게 나누어서 생각해본다. (양끝이 같지않은 부분은 따로 표기를 하지 않았다)
* 1단계
1개의 문자열은 그 자체로 팰린드롬이다.
* 2단계
2개의 문자열로 나누어서 팰린드롬인지 확인한다.
"ab"
"bc"
"cd"
"dd" => 양끝이 같은가? yes
"dc"
"cb"
"be"
* 3단계
3개의 문자열로 나누어서 확인한다.
"abc"
"bcd"
"cdd"
"ddc"
"dcb"
"cbe"
* 4단계
4개의 문자열로 나누어서 확인한다.
"abcd"
"bcdd"
"cddc" => 양끝이 같은가? yes => *[그 다음 양끝이 같은가? yes]*
"ddcb"
"dcbe"
...
* 6단계
6개의 문자열로 나누어서 확인한다.
"abcddc"
"bcddcb" => 양끝이 같은가? yes => *[그 다음 양끝이 같은가? yes => 그 다음 양끝이 같은가? yes]*
"cddcbe"
작은 문제부터 시작하면서 6단계에서 확인할때 4 단계에서 비교한 부분을 중복해서 비교하고있다.
마찬가지로 4단계에선 2단계에서 이미 비교한 부분을 중복해서 비교하고 있다.
전 단계의 결과를 저장해놨다면 6단계에서 양끝이 같은지만 확인하고
내부 문자열의 검사 결과를 확인만 하면 더이상 깊이 파고 내려가면서 비교하지 않고도
해당 문자열이 팰린드롬인지 바로 알 수 있다!
그럼 어떻게 코드를 짜야할지 알아보자.
function solution(s){
let answer = 1;
const len = s.length;
const dp = new Array(s.length).fill(0).map(el => new Array(len).fill(false));
for(let i = 0; i < len; i++){
dp[i][i] = true;
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 = i;
}
}
}
console.log(count)
return answer;
}-
dp 배열을 만들어 준다. i 인덱스에서 j 인덱스까지 팰린드롬인지 확인한 결과를 저장할 배열이기 때문에 2중배열로 false를 채워 넣어준다.
-
자기자신은 언제나 팰린드롬이다. 반복문으로 s.length 만큼 순회하며
dp[ i ][ i ] = true를 할당 해준다.
- 2-1. 동시에 위 반복문에서 2개의 문자열에 대한 비교도 가능하기 때문에
s[ i ]와 s[ i+1 ]의 문자열이 같다면 dp[ i ][ i+1 ] = true 를 할당해준다.
console.log(dp[1][1]) // true
// s의 1번째 인덱스부터 1번째 인덱스까지의 문자열이 팰린드롬인지 boolean 타입으로 저장되어있다.
// 마찬가지로 dp[0][4] 는 0번째 인덱스부터 4번째 인덱스의 문자열이 팰린드롬인지 나타낸다.-
길이 2의 문자열까지 저장해놨으므로, 이제 길이 3의 문자열부터 확인해준다.
반복문은 i = 3부터 시작하며, 중복루프의 start는 0번째 인덱스부터 확인 할 것임을 나타낸다.
0,2번째 인덱스 값이 같은지 확인하고, 1,3번째 확인, 2,4번째 확인...
이렇게 검사를 진행할 것이기 때문에 (end = start + i - 1) 이다.반복문이 어떻게 동작하는지 코드를 보면 이해가 될 것이다.
-
인자로 전달받은 s의 [start] 인덱스와 [end] 인덱스의 문자열이 같다면 dp에 저장되어있는
dp[ start+1 ][ end -1 ]의 값을 확인한다.
해당값이 true 라면 s[ start ] ~ s[ end ] 까지의 문자열은 팰린드롬이다. 더 이상 내부의 값을 비교하지 않아도 된다.
지금의 결과값도 저장해놔야 다음 큰 문제에서도 활용을 할 수 있기 때문에
dp[ start ][ end ] = true를 할당한다.
- 아직 해당 문자열이 제일 긴 문자열인지는 확인 할 수 없으니 현재까지의 문자열 길이를 answer 변수에 할당해주고 반복문을 계속 진행한다.
- 반복문이 종료된 후에 answer 를 return 해준다.
마무리
사실 블로그를 정리하다가 dp알고리즘을 사용하지 않고 이 문제를 풀어버려서 그런지 감흥은 좀 덜하지만 예전에 코린이 시절에 dp 알고리즘으로 문제 푸는걸 봤을때 동작이 이해 안가지만 와 이게 이렇게 풀린다고? 라면서 엄청 신기해 했었다. 그리고 어렵다.. dp알고리즘을 써서 해결할 수 있는지 파악하는것부터 어려운 일인 것 같다.
이 문제의 경우는 결국 풀지 못해서 검색을 해보니 dp알고리즘을 써서 풀 수 있다고 해서 그렇구나 한거지 과연 비슷한 문제를 앞에두고 dp알고리즘을 떠올릴 수 있을지는 확신할 수 없다. 아니 그래도 이제는 혹시나..! 정도는 생각할 수 있을것도 같다. 글 정리하느라 하루종일 쳐다봤는데!
이 문제 말고 프로그래머스 4단계 dp 문제도 있는데.. 그것은 좀 시간을 갖고 정리 해야겠다. 이 블로그를 정리하는데 시간을 무진장 잡아먹었다.
