[파이썬 알고리즘 인터뷰] 1. 유효한 팰린드롬

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 

---

1. 유효한 팰린드롬

 

문제 : 주어진 문자열이 팰린드롬인지 확인하는 문제입니다. 대소문자를 구문하지 않으며, 영문자와 숫자만을 대상으로 합니다.

 

 

풀이 

1. 슬라이싱 이용한 풀이

 책에서는 re 모듈을 이용해서 입력값을 전처리한 뒤에 슬라이싱을 이용하는 풀이법이 나와있습니다.

 re 모듈 사용법을 익혀둔다면 문자열 관련 문제를 풀 때 유용할것 같습니다.

 

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

    return s == s[::-1]

 

 re.sub에 '[^a-z0-9]' 인자를 입력하여 알파벳과 숫자를 제외한 모든 문자를 지정합니다.

 다음 인자로 '' 를 입력하여 지정한 문자들을 ''로 대체합니다.

 

2. 리스트로 변환하여 풀이

 문자열을 리스트로 변환한 풀이법입니다.

 책에서는 deque는 popleft가 O(1)에 실행되기 때문에 deque를 활용하였습니다.

 

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