[Week1/Day5] [코딩테스트연습] 가장 긴 펠린드롬

[코딩테스트연습] 가장 긴 펠린드롬

문제 설명

※ 주의

본 문제는 일부러 시간복잡도가 오래 걸려도 정답이 나오도록 제한 시간이 넉넉하게 설정되어 있습니다.
본 문제를 정말 빠른 알고리즘으로 풀려면 구글에서 longest palindrom subsequence로 검색을 해보세요.

---

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

제한사항

• 문자열 s의 길이 : 2500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

---

입출력 예

s	answer
"abcdcba"	7
"abacde"	3

입출력 예 설명

입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2
2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.

코드 구현

투 포인터를 이용한 방법

def solution(s):
    def expand(left: int , right: int) -> str:
        while left >= 0 and right <= len(s) and s[left] == s[right-1]:
            left -= 1
            right += 1
        return s[left+1:right-1]

    if len(s) <  2 or s == s[::-1]:
        return len(s)

    result = ''
    for i in range(len(s) -1):
        result = max(result, expand(i, i+1), expand(i, i+2), key=len)
    return len(result)

일반적 풀이 방법

최대 팰린드롬 길이는 찾는 것이 목적이다. 즉, 고정 길이를 움직이면서 팰린드롬이 가능한지 여부를 찾는게 중요 해결 전략이다. 문자열의 최대 길이 부터 1씩 줄여가며 최대 팰린드롬을 찾는다.

예시

문자열 s="abacde"로 주어졌을 때 while` 문을 사용 하는 데 표로 작성해보면 다음과 같다. 이 표에서 길이는 한 칸씩움직이는 길이를 말한다. 문자열 s의 최대 길이는 6이다. 그러므로 6부터 시작해서 1씩 줄여가며 팰린드롬이 가능한지 여부를 찾고, 또한 그 고정 길이를 한칸씩 오른쪽으로 움직이면서 팰린드롬 여부를 찾아 간다.

Start	End	길이
0	5	6
0	4	5
1	5	5
0	3	4
1	4	4
2	5	4

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

    return True


def solution(s):
    for answer in range(len(s), 0, -1): # 문자열 최대 길이에서 하나씩 줄여나갑니다.
        start = 0 # 0에서
        end = answer - 1 # answer 길이까지

        while end < len(s):
            if is_palindrome(s, start, end): # 팰린드롬인지 확인합니다
                return answer; # 팰린드롬이면 그대로 리턴
            start += 1
            end += 1 # 고정길이를 한칸 씩 움직인다.

    return 1 # 한 글자일 경우 1을 리턴합니다.