View in English →

Code › algorithm-study

LeetCode 125 - Valid Palindrome

문자 정제와 두 포인터로 회문을 확인하는 Python 풀이

algorithmleetcodestringtwo-pointerspythonlearning

이 문제는 문자열 안에서 알파벳과 숫자만 남기고, 대소문자를 무시한 뒤 회문인지 확인하는 문제다. 처음에는 새 문자열을 만들어 비교하는 방식이 떠올랐는데, 주어진 문자열에서 바로 양쪽 범위를 좁혀 가는 두 포인터 방식으로도 깔끔하게 풀 수 있다.

문제 링크 & 설명

  • 문제 링크: 125. Valid Palindrome
  • 요약: 문자열 s가 주어졌을 때, 영숫자만 기준으로 보고 대소문자를 무시했을 때 회문이면 true, 아니면 false를 반환하는 문제다.

예를 들어 "A man, a plan, a canal: Panama"는 가운데 문장 부호와 공백을 빼고 보면 앞뒤가 같다. 반대로 "race a car"는 같은 방식으로 정리해도 앞뒤가 맞지 않아서 회문이 아니다.

이 문제에서 중요한 점은 문자열을 그대로 비교하면 안 된다는 것이다. 공백, 쉼표, 콜론 같은 문자는 비교 대상이 아니고, 대문자와 소문자도 같은 문자로 봐야 한다. 그래서 먼저 비교 규칙을 정리한 다음, 그 규칙에 맞게 양쪽 끝에서 문자를 확인해야 한다.

접근 방법

처음 떠올리기 쉬운 방식은 영숫자만 남기고 전부 소문자로 바꾼 뒤, 정제된 문자열을 다시 두 포인터로 비교하는 것이다.

new_str = ""
for ch in s:
    if ch.isalnum():
        new_str += ch.lower()

이렇게 만들면 이후 비교는 단순해진다. 하지만 새 문자열을 따로 만들기 때문에 추가 공간이 필요하고, 정제 단계와 비교 단계를 둘 다 거치게 된다.

그래서 최종 풀이는 원본 문자열을 그대로 두고, left와 right 포인터를 양쪽 끝에서 안쪽으로 좁혀 가는 방식으로 정리했다. 영숫자가 아닌 문자는 건너뛰고, 비교할 때만 소문자로 바꿔서 확인한다.

s[left]가 영숫자가 아니면 left를 오른쪽으로 옮기고, s[right]가 영숫자가 아니면 right를 왼쪽으로 옮긴다. 양쪽이 모두 비교 가능한 문자면 소문자로 바꾼 뒤 같은지 확인한다. 다르면 바로 false를 반환하고, 같으면 두 포인터를 한 칸씩 더 안쪽으로 옮긴다.

이 방식은 새 문자열을 만들지 않으므로 공간 복잡도 측면에서 유리하다.

트러블 슈팅

이 문제에서 헷갈리기 쉬운 부분은 비교 대상과 비교 순서를 분리하는 일이다.

먼저, 공백이나 문장 부호를 그냥 무시하면 되는 것처럼 보여도 실제로는 양쪽 포인터가 같은 규칙으로 건너뛰어야 한다. 한쪽만 건너뛰면 비교 위치가 어긋난다. 그래서 left와 right 둘 다 같은 조건으로 isalnum()을 확인해야 한다.

두 번째는 대소문자 처리다. "A"와 "a"는 같은 문자로 봐야 하므로, 비교할 때마다 소문자로 맞춰야 한다. 이 정규화는 비교 직전에 해도 되고, 미리 전부 바꿔도 된다. 다만 미리 새 문자열을 만들면 공간이 추가되니, 원본을 유지한 채 비교 직전에 변환하는게 좀 더 낫다.

마지막으로, 문자열이 거의 전부 특수문자인 경우도 생각해야 한다. 이때는 포인터가 여러 번 건너뛰더라도 결국 가운데에서 만나게 되고, 비교할 영문이나 숫자가 없으면 회문으로 처리된다. 빈 문자열도 같은 규칙으로 보면 true다.

복잡도 분석

  • 시간 복잡도: O(n)

    • left와 right 포인터가 각각 문자열 끝에서 시작해 가운데로 한 번씩만 이동한다.
    • 각 문자는 많아야 한 번씩 건너뛰거나 비교된다.

  • 공간 복잡도: O(1)

    • 원본 문자열 외에 추가로 큰 자료구조를 만들지 않는다.
    • 포인터와 비교용 변수만 사용한다.

전처리를 통해 문자열을 따로 만드는 방식은 직관적이지만, 그 경우 공간 복잡도는 O(n)이 된다.

구현 코드

최종 코드는 원본 문자열에서 투 포인터를 움직이는 방식으로 정리했다.

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

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

            if not s[right].isalnum():
                right -= 1
                continue

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

            left += 1
            right -= 1

        return True

요약 및 회고

이번 문제는 Easy 문제이지만 자칫 잘못하면 꼬여서 짜증이 날 수도 있는 문제다. 문제를 얼마나 단순하게 바라볼 수 있느냐가 중요한 것 같다.