파이썬으로 문자열 좌우를 잘라 만들 수 있는 회문의 개수 구하기

문자열 s가 주어졌을 때, s의 왼쪽과 오른쪽 끝을 잘라내어(트리밍하여) 회문을 만들 수 있는 방법의 총개수를 구하는 문제입니다.

예를 들어 입력이 s = "momo"라면 출력은 6이 됩니다. 좌우를 다양하게 잘라내면 "m", "o", "mom", "m", "omo", "o"처럼 여섯 가지 회문을 얻을 수 있기 때문입니다.

접근 방법: 중심 확장(Center Expansion)

이 문제는 사실 "문자열 안에 존재하는 회문 부분 문자열(palindromic substring)의 개수 세기"와 같습니다. 어떤 방식으로 좌우를 잘라내더라도 결과물은 항상 s의 연속된 부분 문자열이 되고, 우리는 그중 회문인 경우만 세면 되기 때문입니다.

가장 효율적인 해법은 각 인덱스를 회문의 중심으로 삼아 양쪽으로 뻗어 나가는 중심 확장 기법입니다. 이때 중심은 두 가지 경우로 나뉩니다.

• 홀수 길이 회문: 한 문자를 중심으로 확장 — expand(i, i)
• 짝수 길이 회문: 인접한 두 문자 사이를 중심으로 확장 — expand(i, i+1)

알고리즘 단계

1. expand(i, j, s) 함수를 정의하고, 카운터 c를 0으로 초기화합니다.
2. i가 0 이상이고, j가 문자열 길이 미만이며, s[i] == s[j]인 동안 반복합니다.
3. 반복할 때마다 i는 1 감소, j는 1 증가시키고 c를 1 증가시킵니다.
4. 조건이 깨지면 c를 반환합니다.

메인 solve 메서드에서는 모든 인덱스 i에 대해 expand(i, i, s)와 expand(i, i+1, s)를 각각 호출해 그 합을 누적한 뒤 반환하면 됩니다.

구현 예제

def expand(i, j, s):
    c = 0
    while i >= 0 and j < len(s) and s[i] == s[j]:
        i -= 1
        j += 1
        c += 1
    return c

class Solution:
    def solve(self, s):
        c = 0
        for i in range(len(s)):
            c += expand(i, i, s)
            c += expand(i, i + 1, s)
        return c

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

입력

"momo"

출력

6

복잡도 분석

시간 복잡도: O(n²) — n은 문자열의 길이입니다. 총 2n−1개의 중심에 대해 각각 최악의 경우 문자열 끝까지 확장할 수 있습니다.

공간 복잡도: O(1) — 별도의 저장 공간 없이 카운터 변수만 사용하므로 매우 효율적입니다.