파이썬으로 O(1) 추가 공간만 사용해 문자열의 알파벳이 회문을 이루는지 확인하는 방법

문제 개요

문자열 s가 주어졌다고 가정해 보겠습니다. 이 문자열에는 소문자 알파벳뿐만 아니라 특수 문자나 숫자도 섞여 있을 수 있습니다. 우리가 확인해야 할 것은 문자열에서 알파벳 문자만 추출했을 때 회문(palindrome)을 형성하는지 여부입니다. 여기서 중요한 제약 조건은 O(1)의 추가 공간, 즉 별도의 추가 메모리를 사용하지 않고 문제를 해결해야 한다는 점입니다.

예를 들어 입력이 s = "ra$5ce58car"라고 해보겠습니다. 숫자와 특수 문자를 무시하고 알파벳만 읽으면 "racecar"가 되는데, 이는 앞뒤가 같은 회문이므로 결과는 True입니다.

문제 해결 접근 방법

이 문제는 투 포인터(Two Pointer) 기법을 활용하면 추가 공간 없이 해결할 수 있습니다. 문자열의 양쪽 끝에서 시작해 각각 안쪽으로 이동하면서 알파벳 문자만 찾아 서로 비교하는 방식입니다. 구체적인 단계는 다음과 같습니다.

first_letter_index() 함수를 정의합니다. 문자열과 탐색 범위(left, right)를 인자로 받아, 왼쪽부터 오른쪽으로 스캔하면서 처음 만나는 소문자 알파벳의 위치를 반환합니다. 알파벳이 없다면 -1을 반환합니다.
last_letter_index() 함수를 정의합니다. 같은 범위에서 오른쪽부터 왼쪽으로 스캔하면서 마지막(가장 오른쪽) 소문자 알파벳의 위치를 반환합니다.
메인 로직에서는 left = 0, right = len(str) - 1, flag = True로 초기화한 뒤 다음 과정을 반복합니다.
- left := first_letter_index(str, left, right)
- right := last_letter_index(str, right, left)
- left 또는 right가 -1이면 더 비교할 알파벳이 없다는 뜻이므로 반복을 종료합니다.
- str[left]와 str[right]가 같다면 left는 1 증가, right는 1 감소시키고 다음 반복으로 넘어갑니다.
- 두 문자가 다르다면 flag를 False로 설정하고 반복을 종료합니다.
최종적으로 flag 값을 반환합니다.

예제 코드

아래 파이썬 코드를 통해 실제 구현을 살펴보겠습니다.

def first_letter_index(str, left, right):
    index = -1
    for i in range(left, right + 1):
        if 'a' <= str[i] <= 'z':
            index = i
            break
    return index

def last_letter_index(str, left, right):
    index = -1
    for i in range(left, right - 1, -1):
        if 'a' <= str[i] <= 'z':
            index = i
            break
    return index

def solve(str):
    left = 0
    right = len(str) - 1
    flag = True

    for i in range(len(str)):
        left = first_letter_index(str, left, right)
        right = last_letter_index(str, right, left)

        if right < 0 or left < 0:
            break
        if str[left] == str[right]:
            left += 1
            right -= 1
            continue

        flag = False
        break

    return flag

s = "ra$5ce58car"
print(solve(s))

입력

"ra$5ce58car"

출력

True

동작 원리 및 복잡도 분석

위 코드에서 두 포인터는 각각 문자열의 왼쪽 끝과 오른쪽 끝에서 출발합니다. first_letter_index()는 왼쪽에서 오른쪽으로, last_letter_index()는 오른쪽에서 왼쪽으로 이동하며 숫자나 특수 문자를 건너뛰고 알파벳만 찾아냅니다. 찾아낸 두 문자가 일치하면 포인터를 안쪽으로 한 칸씩 이동하고, 일치하지 않으면 즉시 False를 반환합니다. 모든 쌍이 일치하거나 포인터가 교차하면 True를 반환합니다.

이 알고리즘은 문자열 전체를 최대 한 번씩만 스캔하므로 시간 복잡도는 O(n)이며, 포인터 변수 몇 개만 사용하므로 공간 복잡도는 O(1)로 문제의 제약 조건을 충족합니다. 새로운 문자열을 생성해 필터링하는 방식과 달리, 추가 메모리 없이 원본 문자열 위에서 직접 검사한다는 점이 핵심입니다.