문제

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 한다.
문자열 s가 주어질 때, s의 부분문자열중 가장 긴 팰린드롬의 길이를 구하라.

입출력 예시

접근

혼자 해결하지 못하고 해설을 보며 참고했다.
가장 긴 문자열 부터 하나씩 길이를 줄이며 해당 문자열이 팰린드롬인지 검사를 하는 식이다.
solution 함수의 바깥 포문은 부분문자열의 길이를 조정해준다. 전체 문자열의 길이 부터 시작해서 1씩 줄여나간다.
예제를 기준으로 7, 6, 5, 4, …. , 1 로 부분문자열의 길이를 조정한다.
start와 end는 해당 부분문자열의 시작과 끝을 나타낸다.

그 후 while문 에서는 start와 end를 옮기며 해당 길이의 부분문자열을 모두 검사한다.

예를 들어 부분문자열의 길이가 5인 경우, start와 end는 (0, 4), (1, 5), (2, 6) 이다.
그 후는 while문 조건에 의해 걸러진다.
이 경우들을 isPalindrome() 함수에서 팰린드롬 유무를 검사한다.

isPalindrome() 함수의 포문은 현재 부분문자열의 길이를 절반으로 나눈만큼 실행한다.
예를 들어 부분문자열의 길이가 7이라고 하면 for문은 앞뒤의 문자들이 같은지 비교하면 되므로,
부분문자열의 절반만큼 수행하면 전체 문자가 팰린드롬을 이루는지 확인할 수 있다.
이 때 짝수인 경우와 홀수인 경우를 나눠서 생각했는데, 사실 이 함수를 이용하면 두 경우를 나눌 필요가 없었다.
start와 end가 (0, 6)인 경우와 (0, 5)인 경우를 비교해보자.
\(s[0] == s[6]\)
\(s[1] == s[5]\)
\(s[2] == s[4]\)
\(s[3] == s[3]\)

\(s[0] == s[5]\)
\(s[1] == s[4]\)
\(s[2] == s[3]\)

이런식이다.
홀수인 경우 마지막에서 같은 자리를 비교하므로, 마지막까지 온다면 항상 참이다.

코드

• 파이썬 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def solution(s):
    for answer in range(len(s), 0, -1):
        start = 0
        end = answer -1
        while end < len(s):
            if isPalindrome(s, start, end):
                return answer
            start += 1
            end += 1
    return 1   

def isPalindrome(s, start, end):
    for i in range((end-start)//2 + 1):
        if s[start+i] != s[end - i]:
            return False
    return True