[알고리즘] 팰린드롬

팰린드롬이란

문자와 숫자로 이루어진 문자열이며, 뒤집어도 똑같은 문자열

예로 이효리와 같이 뒤집어도 이(리)효리로 같은 문자열을 말한다.

 

팰린드롬인지 확인하는 방법으로 3가지를 만들었습니다.

맨 마지막 방법이 속도면에서 가장 빠른 방법입니다.

 

첫번째 방법은

isalnum()으로 문자열에서 문자와 숫자를 제외한 특수문자 같은 것을 걸러줍니다.

다음, pop()을 사용하여, 앞뒤로 문자를 뽑아주며 팰린드롬인지 확인합니다.

def isPalindrome(s):
    strs=[]
    for char in s:
        if char.isalnum(): 
            strs.append(char)

    # 팰린드롬 여부 판단
    while len(strs) > 1:
        if strs.pop(0) != strs.pop():
            return False
    return True

 

두번째 방법은

첫번째 방법과 같이 isalnum()을 사용 후

pop(0)이 O(n)으로 비효율적이기 때문에 deque를 사용하여, 같은 기능이지만 O(1)인 popleft()를 사용

from collections import deque
def isPalindrome(s):
    strs=deque([])
    for char in s:
        if char.isalnum(): 
            strs.append(char)

    # 팰린드롬 여부 판단
    while len(strs) > 1:
        if strs.popleft() != strs.pop(): # pop(0)은 O(n), popleft()은  O(1)으로 성능향상
            return False
    return True

 

세번째 방법은

정규식을 사용하여 문자와 숫자를 제외한 것 걸러준 후

슬라이싱을 통하여 뒤집어서 원래 문자열과 같은지 확인

import re
def isPalindrome(s):
    s = s.lower()
    s = re.sub("[^a-z0-9]","",s) # 문자와 숫자가 아닌 것은 지우기(""로 대체)
    
    # 팰린드롬 여부 판단
    return s == s[::-1] # 문자열 슬라이싱으로 뒤집기