팰린드롬(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배 정도 속도를 높일 수 있습니다.
'Algorithm > 알고리즘 이론' 카테고리의 다른 글
파이썬으로 구현하는 구간합과 누적합(Prefix sum) (0) | 2024.06.01 |
---|---|
[그래프 탐색] 파이썬으로 구현하는 DFS, BFS (0) | 2023.12.10 |
이진 탐색(Binary Search)과 매개변수 탐색(Parametric Search) (0) | 2022.03.18 |
[그래프 이론] 플로이드-워셜(Floyd-Warshall) 알고리즘 (0) | 2022.01.02 |
네트워크 플로우(Network Flow) (2) | 2021.11.03 |