코테를 위한 기본 알고리즘: 가장 긴 팰린드롬 부분 문자열

안녕하세요! 개발자 여러분, 알고리즘 블로그에 오신 것을 환영합니다. 오늘은 코딩 테스트를 준비하는 데 도움이 되는 기본 알고리즘 중 하나인 "가장 긴 팰린드롬 부분 문자열" 문제를 다루려고 합니다.

 

바로 아래에서 확인하세요~

 

코테를 위한 기본 알고리즘 로고

문제 내용

가상의 문제를 제시해보겠습니다. 주어진 문자열에서 가장 긴 팰린드롬 부분 문자열을 찾는 문제입니다.

 

문제 이해하기

주어진 문자열에서 가장 긴 팰린드롬 부분 문자열을 찾는 것이 목표입니다. 팰린드롬은 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 말합니다.

예를 들어, 주어진 문자열이 "babad"라면, 가장 긴 팰린드롬 부분 문자열은 "bab"이나 "aba"입니다. 이 문제에서는 가장 긴 팰린드롬 부분 문자열을 찾아 그 값을 반환해야 합니다.

 

풀이 코드

pythonCopy code
class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 팰린드롬 판별 및 투 포인터 확장
        def expand(left: int, right: int) -> str:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1:right]

        # 해당 사항이 없을 때 빠르게 리턴
        if len(s) < 2 or s == s[::-1]:
            return s

        result = ''
        # 슬라이딩 윈도우 우측으로 이동
        for i in range(len(s) - 1):
            result = max(result,
                         expand(i, i + 1),
                         expand(i, i + 2),
                         key=len)
        return result

 

풀이 방법

주어진 코드를 통해 가장 긴 팰린드롬 부분 문자열을 찾는 알고리즘을 살펴보겠습니다.

1. 주어진 문자열을 순회하면서 각 문자를 중심으로 하는 팰린드롬을 확장해 나갑니다.
2. 팰린드롬을 확장하는 방법은 투 포인터를 사용합니다. 왼쪽 포인터와 오른쪽 포인터를 설정하고, 왼쪽 포인터가 왼쪽으로 이동하며, 오른쪽 포인터는 오른쪽으로 이동하면서 문자열을 검사합니다.
3. 왼쪽 포인터와 오른쪽 포인터가 문자열 범위를 벗어나거나, 왼쪽과 오른쪽의 문자가 다를 때까지 포인터를 이동시킵니다.
4. 팰린드롬 조건을 만족하지 않으면 현재까지의 팰린드롬 문자열을 반환합니다.
5. 주어진 문자열을 순회하면서 팰린드롬을 찾고, 가장 긴 팰린드롬을 저장하여 반환합니다.

이 알고리즘은 슬라이딩 윈도우와 투 포인터를 활용하여 팰린드롬을 찾는 효율적인 방법입니다.

 

시간 복잡도

이 알고리즘의 시간 복잡도는 O(n^2)입니다. 왜냐하면 주어진 문자열의 길이가 n이라고 할 때, 모든 문자를 중심으로 확장하는 과정에서 최악의 경우에는 각 문자마다 O(n)의 시간이 걸리기 때문입니다.

코딩 테스트에서 이러한 기본 알고리즘을 이해하고 구현할 수 있다면 문제 해결에 큰 도움이 됩니다. 이제 주어진 코드를 기반으로 풀이를 설명하는 포스트를 작성할 수 있을 것입니다. 성공적인 블로깅과 코딩 테스트 준비를 응원합니다!

 

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알고리즘 모음

 

 

백준이 너무 어렵다면 아주 기본 코딩테스트 알고리즘을 먼저 도전해보세요~

 

👉 기본 코딩테스트 문제보기