코딩테스트 문제 (21) - 가장 긴 팰린드롬 부분문자열

문제

가장 긴 팰린드롬 부분문자열 (substring)을 출력하는 문제입니다.

1. 'babad' => 'aba' or 'bab'
2. 'cbbd' => 'bb'

 

풀이

생각해보면 가장 작은 팰린드롬은 2글자 아니면 3글자가 될 수 있습니다. 그렇다면 2칸, 3칸으로 이루어진 슬라이딩 윈도우를 구성하고 이를 왼쪽에서부터 이동시키면서 팰린드롬이면 양쪽의 칸을 한 칸씩 확장하여 팰린드롬인지 확인합니다. 확장한 후 팰린드롬을 확인할 때, 전체를 볼 필요 없이 양 끝값이 같으면 팰린드롬이라고 간단히 판단할 수 있습니다. 이런 방식으로 확장시키면서 팰린드롬일 경우 계속 저장해서 길이가 긴 문자열을 추출하면 되는 문제입니다.

kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다.

 

홍머스 정리

• 난이도: 중

참조

• <파이썬 알고리즘 인터뷰>, p159-161