Algorithm/알고리즘 이론

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

계속지나가기 2023. 11. 25. 17:14
반응형

팰린드롬(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배 정도 속도를 높일 수 있습니다.

반응형