유효한 팰린드롬

문제

주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.

 

입출력 예

s	return
"A man, a plan, a canal: Panama'	true
"race a car"	false

---

풀이

1. 리스트로 변환

def isPalindrome(self, s: str) -> bool:
    strs = []
    for char in s:
        if char.isalnum():
            strs.append(char.lower())   # ['a', 'm', 'a', ...]

    while len(strs) > 1:
        if strs.pop(0) != strs.pop():
            return False 
    return True

영문자, 숫자를 대상으로 한다는 제약조건을 구현하기 위해 isalnum()을 통해 판별하고, 이에 해당하는 경우 strs 배열에 추가한다.이후 팰린드롬 여부를 판별하는데, 영문자와 숫자만 들어있는 배열에 값이 들어있는 동안, 앞과 뒤에서 순차적으로 빼내며 서로 같은지 검사한다. 

 

2. 데크 자료형을 이용한 최적화

-> 리스트를 통해 문제를 풀 경우, 속도가 느린 단점이 있다. 이를 보완하기 위해, 데크 자료형을 이용해 속도를 높여보자.

import collections 

def isPalindrome(s: str) -> bool: 
    strs: Deque = collections.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

print(isPalindrome("abcdedcba"))

collections 모듈의 deque 자료형을 이용하여 데크를 구현하였다. 데크를 이용하여 코드를 수행할 경우 실행속도가 훨씬 개선되는데, 리스트의 pop(0)의 경우 O(n)인데 반해, 데크의 popleft의 경우 O(1)이기 때문이다.

 

3. 슬라이싱 사용

-> 이번에는 파이썬의 리스트 슬라이싱 기능을 활용하여 문제를 풀어보자. 리스트 슬라이싱을 사용할 경우 코드가 훨씬 더 줄어들고, 내부적으로 C로 빠르게 구현되어 있어 훨씬 더 좋은 속도를 기대할 수 있다.

def isPalindrome(s: str) -> bool:
    s = s.lower()
    s = re.sub('[^a-z0-9]', '', s)
    
    return s == s[::-1]

정규식을 통해 문자열 s에 들어있는 문자들 중 a-z와 0-9가 아닌 모든 값들을 공백으로 치환한 뒤, 리스트 슬라이싱을 이용하여 풀었다.

---

Info

1. s[::-1]

-> 문자열을 뒤집는다. 문자열을 뒤집고 뒤집은 문자열이 기존과 같은지 비교하면 팰린드롬 확인 끝 ! 

* reverse 메서드를 이용하여 뒤집을 수도 있는데, 이는 리스트에만 제공되며 문자열의 경우 s = s[::-1]과 같이 사용하면 됨. 다만, 공간 복잡도가 O(1)로 제한되어 있는 경우 오류가 발생할 수도 있는데, 이는 s[:] = s[::-1]과 같이 사용하여 해결할 수 있다. 

2. Deque 

-> collections 모듈의 deque()를 통해 선언할 수 있으며, deque의 경우 popleft를 통해 왼쪽의 값을 빼낼 수 있다. 

3. pop(0)의 시간복잡도 = O(n)