유효한 팰린드롬

팰린드롬이란?

• 앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장을 팰린드롬이라고 합니다.
• 대표적인 예시로는 "abcba"이다. (뒤집어도 같음)

Q. 주어진 문자열이 팰린드롬인지 확인하라.

• 조건: (대소문자를 구분하지 않으며, 영문자와 숫자만을 대상을 한다.)

풀이 1 (리스트 활용)

#유효한 팰린드롬

#풀이 1

def isPalindrome(s):
    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

isPalindrome("abcba")
isPalindrome("abc*d")

실행결과

True
False

주어진 문자열 중 조건에 맞는 영문자와 숫자만을 추출해 strs 리스트에 넣고,
while문을 통해 팰린드롬을 체크하는 형식입니다.

리스트 strs의 길이가 1보다 크다면 ( 리스트에 1개 이상의 원소가 있다면 ),
리스트의 마지막 원소와 첫 원소를 pop 함수를 통해 비교해 다르다면 False를,
while문을 정상적으로 통과하여 나온다면 True를 반환시키는 형식입니다.

풀이2 (데크 활용)

풀이1처럼 pop 함수와 리스트만으로 문제를 해결할 수 있지만, 속도에서는 문제점을 가지고 있습니다. pop함수는 O(n) 의 속도를 가지고 있기 때문입니다. 그래서 속도 측면에서 이점을 가지고 있는 deque를 활용한 풀이입니다.

import collections
def isPalindrome(s):
    strs= 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

풀이를 진행한 아이디어는 풀이1과 같고, 리스트를 데크로 활용한 점이 풀이2의 포인트 입니다.

풀이3 (슬라이싱, 정규표현식 사용)

import re
def isPalindrome(s):
    s=s.lower()
    
    s=re.sub('[^a-z0-9]','',s)
    
    return s == s[::-1] #슬라이싱

눈으로만 봐도 풀이가 위에 2개의 풀이에 비해 간단해진 것을 확인할 수 있습니다. 속도도 풀이2에 비행 2배정도 속도를 높일 수 있습니다. 이렇게 파이썬은 문자열을 슬라이싱할 수 있는 좋은 기능을 제공합니다.

re.sub 는 정규표현식을 사용해 문자열 안에 조건에 맞는 문자를 원하는 문자로 대체하는 방법입니다. 이번 경우에는 a-z,0-9를 제외한 문자를 ''(빈칸)으로 대체했음을 알 수 있습니다. 또한, [::-1]을 통해 문자열을 뒤집을 수 있음을 알 수 있습니다.

• (문제 및 풀이의 출처 , 참고 : 파이썬알고리즘인터뷰 (박상길 지음))