[Programmers] 가장 긴 팰린드롬

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

댓글 남기기