드디어 파이썬알고리즘인터뷰 책의 앞단원인 파이썬에 대한 다지기를 마치고 자료구조,알고리즘에 대해 공부를 하기 시작했다. 오늘은 완전 기초예제부터 풀기 시작했다😊
유효한 팰린드롬
앞서 팰린드롬을 공부한 것을 블로깅한 적이 있다. 그때는 정말 기초만, 정의와 방법 정도만 공부를 했었다. 공백이 들어가거나 문자와 숫자가 섞여 있거나 하는 등의 조금 더 업그레이드 된 예제에 대해서는 풀어보지 않았기 때문에 첫 예제부터 막혀서 풀이를 보며 공부를 하였다. 아직도 문법이나 메서드들에 대한 공부가 많이 필요한 것 같다😂
예제
입력 "A man, a plan, a canal: Panama"
출력 True
-> 대문자, 소문자, 공백, 기호가 섞여있음.
# 함수를 정의할 때 들어갈 변수가 문자열인지 리스트인지 등을 명시해주는게 좋음
# 결과값이 True,False 로 나온다는 것도 써주는게 더 좋음
def isPalindrome(s: str) -> bool:
strs = []
for char in s:
if char.isalnum(): # .isalnum() : 문자(영문,한글), 숫자만 들어있으면 True, 아니면 False
strs.append(char.lower()) # 대문자,소문자가 섞여있기 때문에 전체를 소문자로 통일함
while len(strs) > 1: # 길이가 2 이상이어야 비교가능
if strs.pop(0) != strs.pop(): # 리스트의 제일 앞과 제일 뒤를 비교
return False
return True지금까지의 공부로는 이렇게 풀었었다. 하지만 여기에서 선형 자료구조인 데크Deque를 이용하면 실행속도가 훨씬 빨라진다. 몇달 전에 독학사(컴퓨터공학) 시험을 봤었기 때문에 자료구조를 공부했었다. 그래서 그나마 조금은 빨리 공부할 수 있을 것 같다. 일단 데크는 간단하게 설명하자면 이중연결리스트이다. 양쪽에서 삽입과 삭제를 모두 처리할 수 있다. 후에 더 자세한 내용의 블로그를 올릴 예정이다:)
# 데크는 collections 모듈에서 지원하기 때문에 import로 불러온다
import collections
def isPalindrome(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(): # 리스트의 .pop(0)은 리스트전체를 복사해서 실행하기 때문에 O(n) 이 걸린다. 데크의 .popleft() 는 O(1) 이기 때문에 훨씬 빠르다.
return False
return True리스트를 데크로 선언하는 것만으로도 속도가 훨씬 빨라진다.
그리고 마지막 방법을 하나 더 공부하였다.
알고리즘이라기보다는 정규식과 슬라이싱을 이용한 방법이다.
import re
def isPalindrome(s: str) -> bool:
s = s.lower()
s = re.sub('[^a-z0-9]', '', s) # 정규식으로 불필요한 문자 필터링
return s == s[::-1] # 문자열을 뒤집어서 뒤집기 전과 같은지 비교하여 True or False 리턴❗️ 정규표현식(=정규식)
아직 공부하지 않았기 때문에 다음에 제대로 공부를 하기로 하고 풀이에 나온 부분만 간단하게 구글링, 책을 통해 공부를 했다.
일단, 정규표현식은 복잡한 문자열을 처리할 때 사용하는 기법이며, 파이썬만의 고유 문법이 아니라 문자열을 처리하는 모든 곳에서 사용한다.
일단 위에서 쓴 정규식은 문자 클래스이다. 문자클래스는 [ ]이다. 문자클래스로 만들어진 정규식은 '[ ] 사이의 문자들과 매치' 라는 의미이다.
[ ] 사이에 하이픈(-) 을 사용하면 두 문자 사이의 범위(From-To)를 의미한다. [a-c] 라는 정규식은 [abc]와 같고 [0-4] 라는 정규식은 [01234] 와 같다. 문자 클래스 안에 ^ 이 들어간다면 반대라는 의미를 갖는다.
그래서 위 코드에서 [^a-z0-9] 의 의미는 " a 에서 z 까지의 모든 영소문자와 0 에서 9 까지의 숫자를 제외한 나머지 문자들" 이므로 , 와 : 이 해당된다. re.sub(a,b,c) 는 c에서 a와 매치하는 텍스트를 b로 치환한다라는 뜻이다.
마지막 소스코드처럼 예제를 풀게 되면 코드가 훨씬 더 줄어듬은 물론 위의 다른 두 코드들보다 훨씬 빠른 속도로 실행된다고 한다.
<참고문헌>
박상길, '파이썬 알고리즘 인터뷰', 책만, 2020
박응용, '점프 투 파이썬', 이지스퍼블리싱
