[문자열] 파이썬으로 구현한 유효한 팰린드롬(Palindrome)

팰린드롬(Palindrome)이란?

앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장을 팰린드롬, 우리말로는 회문이라고 부릅니다. 영어의 회문으로는 "No lemon, no melon"처럼 뒤집어도 같은 알파벳 순서를 가지는 문장을 예시로 들 수 있습니다. 예시와 같이 회문은 보통 대소문자와 공백, 특수문자를 구별하지 않습니다. (단, 문제마다 정의하는 회문이 다를 수 있습니다)

 

파이썬으로 유효한 팰린드롬 검사하기

---

자료형에 따른 구현 방법

1. 리스트로 구현

2. 덱(deque)으로 구현

 

각 방법을 보기 전, 입력으로 들어오는 strs은 다음의 정규식을 통해 대소문자/특수문자/공백 구분 없이 유효성을 검사할 수 있도록 처리되었습니다

strs = strs.lower()
strs = re.sub('[^a-z0-9]','',strs)

 

1. 리스트로 구현한 유효한 팰린드롬

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

# 앞의 전처리를 통해 전처리된 strs
strs = list(strs)
if isPalindrome(strs):
    print("회문입니다")
else:
    print("회문이 아닙니다")

 

가장 먼저 생각해볼 수 있는 코드는 리스트로 문자열을 받고, 이를 유효한 팰린드롬인지 검사해보는 코드입니다. 위의 코드와 같이 리스트로 받은 문자열의 맨 앞과 뒷부분에서 pop(0), pop()함수를 이용해 두 문자가 같은지 비교하고, 다를 경우 False를, 해당 조건문에 걸리지 않고 while문을 다 돌았을 때 True를 반환하도록 합니다.

 

하지만, 위의 코드는 while문에서 O(n), if 조건문에서 *pop(0)이 O(n) 시간이 걸리기 때문에 총 시간복잡도는 O(n^2)으로 적지 않은 시간복잡도를 가지는 알고리즘입니다.

*list에서 pop(0)을 할 경우 맨 앞의 요소를 꺼내고 뒤의 요소들을 모두 한칸씩 앞으로 땡겨주어야하기 때문에 리스트의 전체 길이 n만큼의 시간복잡도를 가지게 됩니다

 

 

2. 덱으로 구현한 유효한 팰린드롬

def isPalindrome(strs):
    while len(strs) > 1:
    	if strs.popleft() != strs.pop():
        	return False
    return True
  
from collections import deque
# 앞의 전처리를 통해 전처리된 strs
strs = deque(strs)

if isPalindrome(strs):
    print("회문입니다")
else:
    print("회문이 아닙니다")

그렇다면, pop(0) 동작을 O(1)로 하는 자료형을 사용하면 됩니다. 맨앞과 맨뒤에서 원소를 O(1)의 상수시간으로 꺼내는 자료형으로는 덱(deque)이 있습니다. deque을 사용해 popleft()와 pop()을 사용하여 비교해주면 O(n) 시간에 팰린드롬의 유효성을 검사할 수 있습니다.

 

 

+ 슬라이싱으로 구현한 유효한 팰린드롬

def isPalindrome(strs):
	return strs = strs[::-1]

# 앞의 전처리를 통해 전처리된 strs
if isPalindrome(strs):
    print("회문입니다")
else:
    print("회문이 아닙니다")

마지막으로, 별다른 알고리즘이라고 할 수는 없지만 파이썬의 슬라이싱(sclicing)을 사용한 코드입니다. 슬라이싱을 이용할 경우 코드도 훨씬 짧아지지만 무엇보다 내부적으로 C로 구현되어있기 때문에 앞서 덱으로 구현한 코드보다 2배 정도 속도를 높일 수 있습니다.