[LeetCode/리트코드] No.125, 유효한 팰린드롬(Valid Palindrome) - Python

이 문제는 문자열이 주어졌을 때 그 문자열이 펠린드롬인지 판단하는 문제이다.

 

먼저 펠린드롬이란, 앞뒤가 똑같은 단어나 문장으로 뒤집어도 같은 뜻이 뒤는 단어 또는 문장을 뜻한다. 

ex) '토마토', '소주 만 병만 주소'

 

따라서 그냥 앞뒤가 같은지 확인하는 문제라면, 문자열에 list()를 씌운 뒤 리스트에 이용 가능한 reverse() 함수로 뒤집어도 같은지 확인하면 될 것이다. 그치만 input에 대한 가공이 필요하다.

 

문제에 쓰여있듯이

1. uppercase letters를 lowercase letters로 바꾸어야하고
2. alphanumeric이(영문자 or 숫자) 아닌 문자들은 제거해야한다

문제 분석이 끝났다면 풀이를 진행해보자. 3가지 큰 풀이법을 설명하려고 한다.

 

 

1. isalnum()을 활용하여 문자,숫자만 필터링한 리스트 이용

isalnum(): 파이썬 내장 함수로 '숫자, 한글, 영어' 등이면 True, 다른 문자이면 False를 반환하는 함수이다.

 

풀이1-1

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = []
        for char in s:
            if char.isalnum():
                strs.append(char.lower())
        
        if strs == list(reversed(strs)):
            return True
        else:
            return False

풀이1-1 런타임

해설: for 문을 돌고 나오면 strs 리스트 안에는 숫자,영문자만 소문자로 바뀌어서 차례로 들어올 것이다. 여기서 주의해야 할 점은 append를 진행할 때 lower()를 잊으면 안된다는 것이다. (이것 때문에 나는 5번 정도 에러를 경험해야했다) 

 

다음 if 문에서는 펠린드롬인지 확인하는 코드로 reversed() 함수를 이용했다. 리스트에 적용 가능한 reverse()함수도 있지만 이는 주어진 리스트 자체를 역순으로 바꿔버리는 것이지 반환값이 없기 때문에 이용하지 않았다. 여기서 주의점은 reversed()는 반환값이 있긴 하지만 list로 감싸주어야 우리가 생각하는 형태가 나온다는 점이다.

 

 

 

풀이1-2

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = []
        for char in s:
            if char.isalnum():
                strs.append(char.lower())
        
        while len(strs) > 1:
            if strs.pop(0) != strs.pop():
                return False
        
        return True

해설: isalnum() 함수를 이용하여 숫자와 문자를 골라내는 for문은 똑같이 이어진다.

 

달라지는 부분은 reversed() 함수를 이용하지 않았다는 것인데, 여기서는 반복문 안에서 pop(0) 와 pop() 을 이용하였다. 그 결과 리스트의 길이가 1보다 작거나 같아질 때까지 리스트의 첫 번째 요소와 마지막 요소를 꺼내서 비교하게 된다. pop() 함수 이므로 꺼낸 요소는 리스트에서 사리지는 원리를 이용한다.

 

런타임이 파이썬 자체 함수인 reversed()를 이용할 때보다 늦어진 것을 확인할 수 있다.

이는, 

   스택의 연산인 list.pop() 의 시간 복잡도가 O(1)인 것에 비해

   큐의 연산인 list.pop(0) 의 시간 복잡도가 O(n)이기 때문이다.

 

따라서 우리는 list.pop(0)을 데크를 사용하여 최적화 한 풀이를 생각할 수 있다.

 

 

 

2. 데크를 활용한 최적화 풀이

from collections import deque
class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs: Deque = deque()
        for char in s:
            if char.isalnum():
                strs.append(char.lower())
        
        while len(strs) > 1:
            if strs.popleft() != strs.pop():
                return False
        
        return True

 

 

해설: 먼저 데크 모듈의 popleft() 함수 이용하기 위해 파이썬의 내장 모듈인 collections에서 deque를 import 하였다.(리트코드에서 문제를 풀 때 import 하지 않고 사용해도 정답으로 인정해준다)

 

strs 리스트 명을 그대로 사용하기 위해 strs: Deque = deque() 로 코드를 작성하였고,

이제 시간 복잡도가 O(1) 인 deque.popleft()를 이용하여 list.pop(0)을 대체하였다.

 

시간 복잡도가 눈에 띄게 줄어든 것을 확인할 수 있다.

 

 

 

 

 

3. 정규표현식을 이용한 슬라이싱

from re import sub
class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        s = sub('[^a-z0-9]','',s)

        return s == s[::-1]

해설: 정규표현식을 이용할 때 우리는 re 모듈을 이용하게 된다. 우리는 숫자, 영문자를 제외한 문자를 없애야 하기 때문에 이를 공백을 대체하기 위해 sub() 함수를 이용해야한다. 

sub('[^a-z0-9]','',s) 의 의미는

a-z: a부터 z까지의 문자

0-9: 0부터 9까지의 숫자

^: 이외에는 

'': 공백으로 

sub: 대체한다는 뜻이다.

 

 

이후 슬라이싱을 통해 역순으로 바꿔주고 같은지 비교를 한 boolean 값을 리턴한다.

런타임이 가장 짧은 것을 알 수 있다.

 

 

 

이렇게 펠린드롬 문제에 대해서 다양한 풀이법을 알아보았다. 뒤에 조금 더 심화된 펠린드롬 문제가 나오니 그때를 위해서 다양한 풀이법을 복습해두는 것도 좋을 것 같다.