LeetCode

LeetCode 125 Valid Palindrome 풀이: 양끝 투 포인터 문자열 판정

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문자열에서 영문자와 숫자만 남기고 대소문자를 무시한 뒤 회문인지 확인하는 문제다. 양끝 포인터와 문자 판별 조건을 반복문으로 구현하면 되며, 복잡한 자료구조가 필요하지 않아 Level 2로 판단했다.

1. 문제 요약

문자열 s가 주어질 때 다음 전처리 규칙을 적용한 문자열이 앞에서 읽어도 뒤에서 읽어도 같은지 판정한다.

  • 영문 대문자는 소문자로 바꾼다.
  • 영문자와 숫자가 아닌 문자는 제거한다.
  • 영문자와 숫자는 그대로 비교한다.

전처리 결과가 회문이면 True, 아니면 False를 반환한다. 문자열 길이는 최대 2 * 10^5이고, 출력에서 고려할 문자가 하나도 남지 않는 빈 문자열도 회문으로 취급한다.

예를 들어 ","는 전처리 후 빈 문자열이므로 True이고, "A man, a plan, a canal: Panama"는 "amanaplanacanalpanama"가 되어 True다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

구간 판정

문자열의 양끝에 left, right 포인터를 둔다. 각 포인터가 가리키는 문자가 비교 대상인지 먼저 확인한다.

  • left가 특수문자를 가리키면 오른쪽으로 이동한다.
  • right가 특수문자를 가리키면 왼쪽으로 이동한다.
  • 두 포인터가 유효한 문자에 도착하면 소문자로 바꿔 비교한다.

두 문자가 다르면 즉시 False를 반환한다. 같으면 양쪽 포인터를 한 칸씩 안쪽으로 이동해 다음 쌍을 비교한다. 끝까지 불일치가 없으면 True다.

복사 문자열 없이 양끝의 유효 문자 비교하기

문제에서 요구한 전처리 결과를 실제 새 문자열로 만들 필요가 없다. 비교하는 순간 양쪽의 특수문자를 건너뛰면 전처리 후 문자열에서 서로 마주 보는 문자만 같은 순서로 비교할 수 있다.

따라서 길이가 2 * 10^5인 문자열에서도 필터링된 복사본을 만들지 않고 원본 위치와 두 포인터만 사용해 처리할 수 있다.

상태 전이와 경계 처리

반복 조건은 left < right다. 각 반복에서 특수문자를 건너뛰는 동안에도 두 포인터가 서로 교차하지 않는지 확인해야 한다.

두 포인터가 같은 유효 문자에 도착한 뒤에는 한 번만 비교한다. 모든 문자가 특수문자라서 두 포인터가 비교 전에 만나면 더 비교할 쌍이 없으므로 회문으로 판단할 수 있다. 숫자는 isalnum()이 허용하는 비교 대상에 포함되며, 영문 대소문자는 .lower()로 같은 기준으로 바꾼다.

오답 접근과 반례

대소문자를 그대로 비교하면 다음 입력을 잘못 처리할 수 있다.

s = "A"

한 글자 자체는 회문이며, 대문자와 소문자를 같은 문자로 취급해야 한다. 양쪽 문자를 비교하기 전에 같은 대소문자 기준으로 변환해야 한다.

특수문자를 건너뛰지 않고 바로 비교하면 다음 입력을 잘못 처리한다.

s = "A man, a plan, a canal: Panama"

쉼표, 공백, 콜론을 문자 비교에 포함하면 전처리 후 회문이라는 조건을 반영하지 못한다. 전처리된 문자열을 만들어 뒤집어 비교하는 방법은 정답이지만, 길이에 비례하는 O(n) 추가 공간을 사용한다.

시간·공간 복잡도

각 문자는 포인터가 최대 한 번씩 지나가므로 시간 복잡도는 O(n)이다. 필터링 문자열을 별도로 만들지 않고 포인터만 사용하므로 추가 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1

        while left < right:
            while left < right and not s[left].isalnum():
                left += 1

            while left < right and not s[right].isalnum():
                right -= 1

            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True

isalnum()은 영문자와 숫자를 비교 대상으로 남기는 역할을 한다. 문제의 입력은 출력 가능한 ASCII 문자로 제한되므로 이 판별이 문제 조건과 일치한다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 공백·특수문자·숫자 처리 결과를 확인할 수 있다.

solver = Solution()
assert solver.isPalindrome("A man, a plan, a canal: Panama") is True
assert solver.isPalindrome("race a car") is False
assert solver.isPalindrome(".,!") is True

4. 공식 예제와 추가 검증

공식 예제와 특수문자만 있는 문자열, 숫자와 대소문자가 섞인 문자열을 Python 코드로 실행했다.

공식 예제

입력 기대 출력 확인 결과
"A man, a plan, a canal: Panama" True 통과
"race a car" False 통과
" " True 통과

추가 검증 1: 숫자와 대문자 불일치

입력: s = "0P"
기대 출력: False
확인 결과: 통과
검증 목적: 숫자도 비교 대상에 포함하고 서로 다른 문자를 판정하는지 확인

추가 검증 2: 특수문자 제거 후 한 글자

입력: s = "a."
기대 출력: True
확인 결과: 통과
검증 목적: 특수문자를 건너뛴 뒤 남은 한 문자를 회문으로 처리하는지 확인

추가 검증 3: 비교 대상이 없는 문자열

입력: s = ".,!"
기대 출력: True
확인 결과: 통과
검증 목적: 전처리 결과가 빈 문자열인 경계 확인

추가 검증 4: 문장 전체 비교

입력: s = "Was it a car or a cat I saw?"
기대 출력: True
확인 결과: 통과
검증 목적: 공백과 물음표를 제외한 긴 회문 문장 확인

5. 다른 풀이 방식 검색 및 비교

필터링된 문자열을 ''.join(...)으로 만든 뒤 앞뒤를 비교하면 코드가 짧고 이해하기 쉽지만 O(n) 공간이 필요하다. 이 글에서는 문제의 문자를 직접 확인하면서 특수문자를 건너뛰어 추가 문자열 없이 O(1) 공간을 사용했다.

마무리

Valid Palindrome은 전처리 규칙을 비교 과정에 녹여 내는 양끝 투 포인터 문제다. 유효하지 않은 문자를 양쪽에서 건너뛰고 대소문자를 통일한 뒤 현재 쌍만 비교하면, 별도의 문자열 복사 없이 O(n) 시간과 O(1) 공간으로 회문 여부를 판정할 수 있다.

#투 포인터#LeetCode#난이도 2