파이썬으로 문자열에 짝수 길이 회문 부분 문자열이 포함되어 있는지 확인하는 방법

문제 개요

문자열 s가 주어졌을 때, 이 문자열 안에 짝수 길이의 회문(palindrome) 부분 문자열이 존재하는지 확인해야 합니다.

예를 들어 입력이 s = "afternoon"이라면, "afternoon"에는 짝수 길이의 회문인 "noon"이 포함되어 있으므로 결과는 True가 됩니다.

접근 방식

핵심 아이디어는 매우 간단합니다. 길이가 2 이상인 짝수 길이 회문은 반드시 가운데 두 문자가 서로 같아야 한다는 성질을 이용합니다. 따라서 문자열 전체를 탐색할 필요 없이, 인접한 두 문자가 동일한 경우가 하나라도 존재하는지만 확인하면 됩니다. 그 두 문자 자체가 이미 길이 2의 짝수 회문이기 때문입니다.

알고리즘의 진행 순서는 다음과 같습니다.

• 인덱스 i를 0부터 문자열 길이 - 2까지 순회합니다.
• string[i]와 string[i + 1]이 같으면 즉시 True를 반환합니다.
• 모든 위치를 확인한 후에도 조건을 만족하지 않으면 False를 반환합니다.

이 방식의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(1)로 매우 효율적입니다.

구현 예제

def solve(string):
    for i in range(len(string) - 1):
        if string[i] == string[i + 1]:
            return True
    return False

s = "afternoon"
print(solve(s))

입력

"afternoon"

출력

True

추가 예제

반대로 인접한 같은 문자가 전혀 없는 문자열의 경우 False가 반환됩니다.

s = "python"
print(solve(s))  # 출력: False

정리

짝수 길이 회문의 존재 여부는 결국 "같은 문자가 연속으로 등장하는가"라는 조건 하나로 판별할 수 있습니다. 이처럼 문제의 구조적 성질을 파악하면 불필요한 완전 탐색 없이 선형 시간에 해결할 수 있습니다.