[Leet Code] 125. Valid Palindrome(유효한 팰린드롬)

 

이 글을 보러 들어오신 분들은 문제를 알고 오신 분들이기 때문에 팰린드롬에 대해 추가적인 설명을 하지는 않을게요! 

 

주어진 문자열이 팰린드롬인지 확인하는 문제예요. 다만 주어진 문자열에서 대소문자는 구별하지 않고, 영문자와 숫자만 대상으로 해요. 즉, 특수문자나 공백 문자열 등은 대상에서 제외되겠죠? 

 

📝 풀이

 

어떤 알고리즘을 사용하든 전처리 작업이 필요할 거예요.

책에서는 이것을 for문을 통해서 처리하거나 정규표현식을 통해 처리하는데 저는 조금 다르게 전 처리했어요. 우선 책에서 한 전처리 방법이에요.

 

# 반복문 사용
strs = []
for char in s:
    if char.isalnum():
    	strs.append(char.lower())
        
# 정규표현식 사용
s = re.sub('[^a-z0-9]', '', s)

 

사실 정규표현식이 가장 간단한 방법이에요. 그런데, 막상 코딩 테스트를 풀 때에는 정규표현식에는 손이 잘 안 가더라고요! 그래서 저는 아래와 같이 전처리를 했어요.

 

s = ''.join(list(filter(lambda x: x.isalnum(), s))).lower()

 

filter 메서드는 리스트의 요소 중 특정 조건에 해당하는 요소만 거를 수 있는 함수예요. 사실 파이썬보다 Swift의 고차 함수에서 익숙한 메서드라 검색을 통해 알게 되었어요. 사용법은 filter(조건 함수, 리스트 or 튜플)로 사용하고, 결과물을 리스트나 튜플에 담으면 돼요. 

 

그래서 저는 isalnum 메서드를 통해 s의 요소가 alphabet 또는 number인지 확인하고, 그 결과물을 문자열로 만든 뒤 소문자로 만들어주었어요. lower 메서드가 동작할 때, 요소에 숫자가 있을 경우 에러가 발생하지 않을까 걱정했는데 lower 메서드는 문자열인지 확인한 후 소문자로 만들어주는 것 같아요. 확인해보니 에러가 발생하지 않았어요.

 

그 후 팰린드롬을 확인하면 되는데, 여기에는 크게 두 가지 방법이 있을 것 같아요.

 

첫 번째는 직접 문자열의 맨 앞과 맨 뒤를 비교하고 그 문자열을 잘라가며 확인하는 방법

두 번째는 문자열을 자르는 게 아니라 반복문을 통해 length // 2까지 확인하며 앞과 뒤를 비교하는 방법이에요. 1번 요소와 -1번째 요소, 2번째 요소와 -2번째 요소... 를 비교하는 방법이에요. 

 

저는 첫 번째 방법을 사용했어요.

이 첫번째 방법도 두 가지로 나뉠 수 있을 것 같아요.

 

우선, while 반복을 통해 직접 문자열을 자르며 확인하는 방법과

재귀 함수를 통해 Palindrome을 확인하는 방법이에요. 

 

저는 둘 다 사용해봤어요.

 

# 반복문 사용
def my_solution1(s: str) -> bool:
    from collections import deque
    s = deque(''.join(list(filter(lambda x: x.isalnum(), s))).lower())
    while len(s) > 1:
        if s.popleft() != s.pop():
            return False
    return True
    
# 재귀함수 사용
def my_solution2(s: str) -> bool:
    s = ''.join(list(filter(lambda x: x.isalnum(), s))).lower()
    if len(s) <= 1:
        return True
    if s[0] == s[-1]:
        return my_solution2(s[1:-1])
    return False

 

반복문에서는 문자열을 직접 자르기 때문에 속도를 위해서 deque를 사용했어요. deque를 사용하면 리스트의 .pop(0)이 O(N)인 것에 반해 .popleft()를 통해 O(1)으로 해결 가능하기 때문이에요. 

 

🧐 고민

우선 코드만 보면 재귀 함수가 훨씬 간단해 보여요. 알고리즘이 익숙하지 않은 사람이 봤을 땐 더 좋은 코드라고 생각되기 쉬울 것 같아요. 하지만 재귀 함수는 내부적으로 Stack으로 쌓이고, 파이썬의 경우 Stack의 깊이가 maximum 1000개로 되어있어요. 즉, 재귀가 너무 많이 반복될 경우 Over Flow가 발생할 수 있죠. 

 

물론, set recursion limit를 통해 재귀의 깊이를 높일 수 있어요. 하지만 그런 처리를 하지 않는다면, 분명히 재귀 함수를 통한 풀이는 문제의 조건에 따라 오류를 발생시키는 메서드가 될 수 있어요.

 

그럼 반복문 함수를 살펴볼게요. 반복문 함수의 경우 조금 신경 쓰이는 부분이 2가지 일 수 있을 것 같아요.

 

우선, 반복문 안에 pop이 2번 있기 때문에 빈 리스트에서 pop을 하려고 할 때 발생하는 오류 가능성이 신경 쓰일 수 있어요. 하지만 while 조건에서 길이를 2 이상으로 하고 있기 때문에, 전혀 문제가 없어요. 이 부분을 설명한 이유는 저는 개인적으로 반복문 안에서 pop 하는 로직을 사용할 때 굉장히 조심하기 때문이에요. 

 

두 번째는 popleft와 pop의 동작 순서예요. popleft와 pop 중 어떤 것이 먼저 동작 하나의 문제가 신경 쓰일 수 있는데, 순서로 보면 아마 pop이 먼저 동작할 거예요. 비교나 대입에서 "="의 오른쪽이 먼저 동작하니까요. 하지만 이 로직에선 사실 둘 중 어떤 것이 먼저인지 상관이 없어요. 한쪽에서만 계속 pop을 하면서 어떤 후처리 작업이 다르게 들어가는 경우 문제가 될 수 있지만 여기서는 그런 게 전혀 없이 양쪽에 뽑은 요소를 단순 비교하기 때문에 순서는 상관없어요.

 

단순한 문제이기 때문에 크게 어려운 것은 없었어요! 

이 문제를 통해 얻을 것은 재귀와 반복문으로 구현해보기, filter 메서드 사용법, isalnum, lower에서 문자열이 아니어도 문제가 안된다는 정보 정도였던 것 같아요.

 

 

🐾 문제 링크 가기

https://leetcode.com/problems/valid-palindrome/