Python으로 한 번의 회전 후 만들 수 있는 가장 긴 회문 부분 문자열 길이 구하기

문자열 s가 주어지고, 이 문자열을 임의의 위치에서 정확히 한 번만 회전할 수 있다고 가정해 보겠습니다. 이때 이 연산을 통해 얻을 수 있는 가장 긴 회문(palindrome) 부분 문자열의 길이를 구하는 것이 목표입니다.

예를 들어 입력이 s = "elklev"라고 해보겠습니다. "el"과 "klev" 사이에서 회전하면 "levelk"라는 문자열을 얻을 수 있으며, 여기서 가장 긴 회문 부분 문자열은 "level"이므로 결과는 5가 됩니다.

풀이 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• s2 := 문자열 s를 두 번 이어 붙인 새로운 문자열로 설정
• max_len := 0으로 초기화
• x를 0부터 s의 길이 - 1까지 반복
  • y를 0부터 s의 길이까지 반복
    • temp := s2의 인덱스 x부터 x + y까지의 부분 문자열
    • 만약 temp가 회문이고 temp의 길이가 max_len보다 크다면
      • max_len := temp의 길이로 갱신
• 최종적으로 max_len 반환

핵심 아이디어는 문자열을 두 번 이어 붙이면 모든 가능한 회전 결과가 s2 안에 부분 문자열 형태로 포함된다는 점입니다. 따라서 s2의 모든 부분 문자열을 검사하여 회문인 것 중 가장 긴 것을 찾으면 됩니다.

구현 예제

class Solution:
    def solve(self, s):
        s2 = 2 * s
        max_len = 0
        for x in range(len(s)):
            for y in range(len(s) + 1):
                temp = s2[x : x + y]
                if temp == temp[::-1] and len(temp) > max_len:
                    max_len = len(temp)
        return max_len

ob = Solution()
s = "elklev"
print(ob.solve(s))

입력

"elklev"

출력

5

동작 원리 설명

위 코드에서 temp == temp[::-1]은 파이썬의 슬라이싱 기법을 활용한 회문 판별 방식입니다. 문자열을 뒤집은 결과와 원본이 같다면 그 문자열은 회문입니다.

시간 복잡도 측면에서 이 방법은 O(n³)에 해당합니다. 시작 인덱스 x와 길이 y를 선택하는 데 O(n²), 각 부분 문자열의 회문 여부를 확인하는 데 O(n)이 소요되기 때문입니다. 문자열의 길이가 짧은 경우에는 충분히 실용적이지만, 더 긴 입력에 대해서는 중심 확장(center expansion) 기법 등 최적화된 회문 탐색 알고리즘을 적용하는 것을 고려할 수 있습니다.