팰린드롬이란 ?
앞뒤가 똑같은 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장을 팰린드롬(Palindrome)이라고 한다. 우리말로는 ‘회문’이라고 부르며, 문장 중에서는 대표적으로 ‘소주 만 병만 주소’ 같은 문장이 이에 해당한다. 이 문장은 뒤집어도 ‘소주 만 병만 주소’가 된다. 이러한 팰린드롬의 특징을 응용하면 여러 가지 재밌는 문제들을 많이 만들어낼 수 있기 때문에 코딩테스트에 매우 자주 출제되는 주제이기도 하다. 이 책에서는 다양한 팰린드롬 응용 문제들을 풀이해본다.
풀이 1 ) 리스트로 변환
def isPalindrome(self, s:str) -> bool :
strs = []
for char in s :
if char.isalnum():
strs.append(char.lower())
# 팰린드롬 여부 판별
while len(strs) > 1 :
if strs.pop(0) != strs.pop() :
return False
return True
- isalnum() : 영문자, 숫자 여부를 판별하는 함수.
- lower() : 모두 소문자로 변환
풀이 2 ) 데크 자료형을 이용한 최적화
데크를 명시적으로 선언하면 좀 더 속도를 높일 수 있다. 풀이 1의 경우 실행에 304밀리초가 걸렸다.
Deque는 스택과 큐를 합친 구조이다. 가장자리에 원소를 빼거나 넣을 수 있다.
스택과 달리 큐를 list로 이용하지 않는 이유
스택과 달리 큐를 list로 이용하지 않는 이유
스택에서 list.append와 list.pop()을 이용했던 것처럼 list.append와 list.pop(0)을 이용하면 리스트를 큐처럼 사용할 수 있다. 하지만 pop()의 time complexity는 O(1)인 반면 pop(0)의 time complexity는 O(N)이기 때문에 시간이 오래 걸린다. 따라서 시간 복잡도를 고려해 리스트는 큐로 사용하지 않는다.
def isPalindrome(self, s:str) -> bool :
strs: Deque = 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
자료형을 데크로 선언하는 것만으로 5배 가까이 속도를 높일 수 있다. 이는 리스트의 pop(0)는 $O(n)$인데 반해 데크의 popleft()는 $O(1)$이기 때문이다.
풀이 3 ) 슬라이싱 사용
파이썬에서는 문자열 슬라이싱이라는 매우 편리한 기능을 제공한다. 무엇보다 내부적으로 매우 빠르게 동작한다. 위치를 지정하면 해당 위치의 배열 포인터를 얻게 되며 이를 통해 연결된 객체를 찾아 실제 값을 찾아내는데, 이 과정은 매우 빠르게 진행되므로 문자열을 조작할때는 항상 슬라이싱을 우선으로 사용하는 편이 속도 개선에 유리하다. 문자열을 별도로 리스트로 매핑하는 등의 처리는 데이터 구조를 다루는 입장에서는 좋은 방법이지만, 별도 자료형으로 매핑하는 과정에서 상당한 연산 비용이 필요하므로 전체적인 속도에서는 오히려 손해를 볼 수 있다. 대부분의 문자열 작업은 슬라이싱으로 처리하는 편이 가장 빠르다.
‘안녕하세요’ 문자열을 s[1:4]로 슬라이싱한 결과
- s[1:-2] == ‘녕하’
- s[1:] == ‘녕하세요’
- s[:] == ‘안녕하세요’
- s[1:100] == ‘녕하세요’
- s[-1] == ‘요’
- s[:-3] == ‘안녕’
- s[-3:] == ‘하세요’
- s[::1] == ‘안녕하세요’
- s[::-1] == ‘요세하녕안’ : 뒤집음
- s[::2] == ‘안하요’
import re
def ispalindrome(self, s:str) -> bool :
s = s.lower()
#정규표현식으로 불필요한 문자 필터링
s = re.sub('[^a-z0-9]','',s)
return s[::-1]
- re.sub()
- re.sub(pattern, new, string)
- string에서 pattern에 해당하는 부분을 new로 대체하라는 의미