Programmers Lv.3 가장 긴 팰린드롬
[문제]
문제 설명
앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.
예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.
제한사항
문자열 s의 길이 : 2,500 이하의 자연수
문자열 s는 알파벳 소문자로만 구성
[접근 방법]
일단 처음으로 생각했던 건 팰린드롬이라는 게 어차피 가운데를 기준으로 좌우 반전 시켰을 때 동일한 문자열이어야 하니까 계속 절반을 나눠서 팰린드롬이 나타나면 max값을 계산해 return 해주면 되지 않을까 생각했지만, 일단 그 코드는 틀리고 시간이 오래 걸렸다. 그리고 가장 큰 문제는 팰린드롬이 꼭 정확히 문자열의 절반의 절반의 절반을 기준으로 나타나지 않는다는 것이다. 그래서는 전체 케이스를 커버할 수 없다.
그래서 반대로 return 해야 하는 값이 가장 긴 팰린드롬인 점을 이용했다. 팰린드롬은 주어진 문자열의 substring이므로 어차피 최대 길이가 주어진 문자열의 길이와 같다. 그렇다면 전체 길이에서 계속 줄여나가서 만약 2보다 큰 팰린드롬이 있으면 바로 그 길이를 return해주면 된다. 만약 길이가 2보다 크거나 같은 팰린드롬이 없다면 전체 문자열에 대해 좌우 대칭되는 문자열이 없다는 뜻이므로 1을 return하면 된다.
해당 길이에서 팰린드롬을 찾는 방법은 문자열 처음부터 찾는 문자열의 size만큼 잘라서 해당 문자열이 팰린드롬인지 확인해주는 작업을 거치면된다. (s.substring(0,size) ~ s.substring(i,i+size))
예를 들어 주어진 문자열의 길이가 7이면
size(length) = 7 -> s.substring(0,7) : 한 번만 확인하면 된다.
size(length) = 6 -> s.substring(0,6), s.substring(1,7) : 두 번 확인해준다.
이런 식으로 2까지 확인해주면 된다.
팰린드롬 확인하는 방법은, 위에서 설명한대로 주어진 문자열 가운데 인덱스를 기준으로 좌우를 비교해주면 된다.