[파이썬 알고리즘] 유효한 팰린드롬

유효한 팰린드롬

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

팰린드롬이란, 앞뒤가 똑같은 단어나 문장을 뜻한다.

"A man, a plan, a canal: Panama" -> True

---

문제를 보고 생각난 해답법은 다음과 같았다.

(palindrom_1.py)

1. 문자열의 길이를 구해 2로 나누어 몫을 구한다 -> halfLen
2. 문자열의 (0, -0), (1, -1) ... (halfLen, -halfLen)의 인덱스가 서로 같은지 검사한다
3. 끝까지 실행되면 true, 중간에 다르면 false로 리턴

def isPalindrom(s: str) -> bool:
    s_len = len(s) // 2

    for i in range(s_len):
        if(s[i] != s[-(i+1)]):
            return False

    return True

결과적으로 위의 해답은 반쪽짜리이다.

우선 입력값이 비어있을 때의 예외처리를 하지 않았으며 Lowercasing, 공백 및 특수문자(, .와 같은) 의 경우를 생각하지 않았다.

따라서 위의 프로세스에 전처리 과정을 추가하였다.

def preprocess(s: str) -> str:
    result = []
    for char in s:
        if char.isalnum():
            result.append(char.lower())

    return result

결과적으로 잘 동작하게 되었으나, 여전히 몇 가지의 문제점을 발견할 수 있다.

다음과 같이 필요없는 for문을 줄여 깔끔하게 바꿀 수 있다.

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

하지만 위와 같이 구현하게 되면, 파이썬의 리스트에서 pop(0)은 O(n) 이므로, 기존의 인덱스를 통해 리스트의 요소에 접근하는 O(1)과 대비하여 속도가 느려진다.

이를 해결하기 위해 파이썬의 collections.deque() 자료형을 사용할 수 있는데, deque에서 popleft() 는 O(1) 이다.

(palindrome_3.py)
strs: Deque = collections.deque()
~~~
while len(strs) > 1:
    if strs.popleft() != strs.pop():
        return False
return True

다음으로, 슬라이싱과 정규식을 통하여 이 문제를 해결할 수도 있다.

(palindrome_4.py)
~~~
s = s.lower()
s = re.sub('[^a-z0-9]', '', s)

return s == s[::-1] # 슬라이싱

정규식으로 불필요한 문자를 필터링하고, 문자열을 조작할 수 있는 파이썬의 슬라이싱을 활용한다.

파이썬은 문자열을 배열이나 리스트처럼 슬라이싱할 수 있는 기능을 제공하며,
[::-1]을 이용하여 뒤집을 수 있다.

코드가 매우 간결하며 내부적으로 C로 빠르게 구현되어 있어 성능 역시 좋다.