Link : Lv3. 가장 긴 팰린드롬
- 문제 설명
앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를
return 하는 solution 함수를 완성해 주세요.
예를들면, 문자열 s가 abcdcba
이면 7을 return하고 abacde
이면 3을 return합니다.
제한사항
- 문자열 s의 길이 : 2500 이하의 자연수
- 문자열 s는 알파벳 소문자로만 구성
- 문제 풀이
단순히 첫 문자에서 부터 끝 문자까지 Palindrome을 찾는 문제가 아니라
부분 문자열 중에 가장 긴 Palindrome을 찾아야 한다.
이 문제도 부분을 확실하게 다진 다음 확장해 나가는 방법을 써 보겠다.
만약에 위에 녹색 부분인 세 개의 문자가 Palindrome인 것을 안 다면,
위에 파란색 부분만 같은 문자라면 부분 문자열 5개는 Palindrome이라 할 수 있다.
이런식으로 부분이 Palindrome 인지 조사를 해가면서 가장 긴 Palindrome 문자열을 찾는 것이다.
먼저 문자열 s 가 있으면 임의의 문자 위치 i … j 까지가 Palindrome 인지 표시하는 배열(table)을 둔다.
모든 한 개의 문자는 Palindrome 이므로 table[0][0], table[1][1] … 은 모두 true로 둔다.
그 다음 연속 된 두 개의 문자도 조사하여 같은 문자면 table[0][1], table[1][2] … true로 둔다.
그리고 나머지는 3개 부터 문자열 길이 n개 까지를 조사해 나가는 것이다.
효율성은 거의 BigO(n²) 이 될 것이다.
Source Code : the_longest_palindrome.cpp