📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님'을 보고 작성되었습니다.
😎문제 : https://leetcode.com/problems/valid-palindrome
[유효한 팰린드롬]
[팬린드롬이란?]
회문 또는 팰린드롬은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다.
출처: https://ko.wikipedia.org/wiki/%ED%9A%8C%EB%AC%B8
[일반 리스트를 사용한 방법]
class Solution:
def isPalindrome(self, s: str) -> bool:
lst = []
for i in s:
if i.isalnum():
lst.append(i.lower())
# 팰린드롬 여부 판별
while len(lst) > 1:
if lst.pop(0) != lst.pop():
return False
return True
isalnum( )
은 영어, 숫자인지를 판별해주는 함수이다.lower( )
은 입력 받은 문자가 전부 소문자로 바꿔주는 함수이다.
[deque 자료형을 이용한 최적화]
from collections import deque
class Solution:
def isPalindrome(self, s: str) -> bool:
lst = deque()
for i in s:
if i.isalnum():
lst.append(i.lower())
# 팰린드롬 여부 판별
while len(lst) > 1:
if lst.popleft() != lst.pop():
return False
return True
- pop(0)보다 popleft( )가 훨씬 빠르게 작동한다. 그렇기 때문에 맨 앞의 요소를 꺼내서 빈칸을 위해 맨 앞의 바로 뒤 요소를 다 옮겨야 되는 pop이 아닌 popleft( )를 사용하도록 하자
- deque는 스택처럼 쓸 수도 있고, 큐처럼 사용도 가능하다.
[슬라이싱을 사용한 방법]
class Solution:
def isPalindrome(self, s: str) -> bool:
s = s.lower()
#정규식을 사용한 불필요한 문자 필터링
s = re.sub('[^a-z0-9]','',s)
return s == s[::-1] #슬라이싱
s = s.lower()
- 문자열을 소문자로 만들어준다.s = re.sub('[^a-z0-9]','',s)
- 정규식을 사용해 영문, 숫자만 남긴다.s == s[::-1]
- 남긴 문자와 s[::-1] 뒤집은 문자가 같은지를 비교 연산자를 통해 확인하고 돌려준다.
[실행 속도 비교]
위에서부터 슬라이싱, 데크 자료형 이용, 리스트 이용 해서 푼 경우다.
어떻게 알고리즘을 구성하느냐에 따라서 Runtime이 몇배씩 차이가 나는 걸 볼 수 있다.
[참고 C언어]
C언어로 이 문제를 풀었다면 포인터를 직접 조작하는 방식으로 진행해서 매우 짧은 시간에 이를 해결한다.
파이썬은 인터프리터 언어로 컴파일 언어인 C보다 성능이 조금 더 떨어지는 걸 알수 있다.
'자료구조와 알고리즘 > 🥑알고리즘' 카테고리의 다른 글
[알고리즘][문자열 조작] - 여러가지 정렬 방법 (0) | 2022.02.17 |
---|---|
[알고리즘][문자열 조작] - 5. 그룹 애너그램 (0) | 2022.02.16 |
[알고리즘][문자열 조작] - 4. 가장 흔한 단어 (0) | 2022.02.16 |
[알고리즘][문자열 조작] - 3. 람다와 +연산자를 이용 (0) | 2022.02.16 |
[알고리즘][문자열 조작] - 2. 문자열 뒤집기 (0) | 2022.02.14 |