가장 긴 팰린드롬-프로그래머스(python)

JunSung Choi·2020년 3월 6일
1

알고리즘

목록 보기
10/20
post-thumbnail

문제 링크 : 가장 긴 팰린드롬-프로그래머스

문제 설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(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를 리턴해준다.

profile
Frontend Developer

3개의 댓글

comment-user-thumbnail
2020년 10월 29일

효율성2에서 런타임에러가 나네요 ㅜ

2개의 답글