문제 링크 : 가장 긴 팰린드롬-프로그래머스
앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.
예를들면, 문자열 s가 abcdcba이면 7을 return하고 abacde이면 3을 return합니다.
문자열 s의 길이 : 2,500 이하의 자연수
문자열 s는 알파벳 소문자로만 구성
입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.
입출력 예 #2
2번째자리 'b'를 기준으로 aba가 팰린드롬이 되므로 3을 return합니다.
def palindrome(string):
if len(string) <= 1:
return True
if string[0] == string[-1]:
return palindrome(string[1:-1])
else:
return False
def solution(s):
for cut in range(len(s), 0, -1):
for start in range(0, len(s)):
cutStr = s[start:start+cut]
# 자른 string 전달
if palindrome(cutStr) == True:
return len(cutStr)
if start+cut >= len(s):
break
재귀와 리스트의 slice를 이용해서 풀었다. 먼저 테스트 케이스로 주어진 문자열 길이부터 1씩 감소하며 문자열 길이가 1일때까지 반복문을 돈다. 문자열 길이부터 먼저 도는 이유는 가장 긴 팰린드롬을 찾는것이기 때문이다. 그리고 잘라낼 길이를 기준으로 string을 적절하게 잘라 palindrome 함수에 파라미터로 전달하며 호출해줬다. palindrome 함수는 재귀로 구성했다. 문자열의 제일 앞부분과 제일 뒷부분을 비교하고 같으면 그 다음의 앞, 뒤 를 다시 파라미터로 전달하며 palindrome을 호출해준다. 팰린드롬이면 문자열 길이가 1일때까지 호출할 것이며 그게 곧 팰린드롬인것이다. 한번이라도 앞, 뒤 문자열이 달랐으면 False를 리턴해준다.
효율성2에서 런타임에러가 나네요 ㅜ