

Palindrome(팰린드롬) 이란 무엇일까?
팬린드롬이란 앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장이다
예를 들어 '토마토' 'level' 같은 단어들이 팬린드롬이라 할 수 있다.
이 문제는 주어진 문자열이 팰린드롬인지 확인하는 문제이다.
대소문자는 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.
1. 📌 첫번째 풀이 : 리스트로 변환
직접 문자열을 받아 단어가 영문자 또는 숫자인지 확인한다 (특수문자인 것을 거르기 위한 작업)
strs = []
for char in s:
if char.isalnum():
strs.append(char.lower())
여기서 isalnum( ) 메소드는 영문자, 숫자 여부를 판별하는 함수로, 이를 이용해 해당하는 문자만을 strs리스트에 추가해준다.
만약 여기에 ' l,e,v,e,l ' 과 같은 문자열이 들어간다면 strs에는 [ 'l', 'e', 'v', 'e', 'l' ] 다음과 같이 담게기 된다.
이제 팰린드롬 여부를 확인해야 한다.
while len(strs) > 1:
if strs.pop(0) != strs.pop():
return False
return True
파이썬의 리스트는 pop( ) 함수에서 인덱스를 지정할 수 있기 때문에 인덱스를 0으로 지정해 주어 첫글자와 마지막 글자를 비교해준다.
모두 통과했다면 True를 리턴한다.
전체 코드는 다음과 같다. (리트코드 제출방식)
class Solution:
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
2. 📌 두번째 풀이 : 데크 자료형을 이용한 최적화
만약 데크를 사용한다면 어떨까? 아마 처리속도가 더 증가하게 될것이다.
그저 리스트를 데크로만 변경해보겠다
class Solution:
def isPalindrome(self, s: str) -> bool:
strs = 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
똑같은 알고리즘이지만
리스트를 데크로 변경시켜주었고 pop(0) -> popleft( ) 로 변경시켜주었다.
시간을 확인해본 결과
- 리스트 -> 296ms
- 데크 -> 52ms
로 6배 정도 시간차이가 나는 것을 확인할 수 있었다.
'Algorithm' 카테고리의 다른 글
백준 알고리즘 파이썬(Python) 10819번 차이를 최대로 (0) | 2021.09.05 |
---|---|
리트코드(LeetCode) 937번 로그 파일 재정렬(Reorder Data in Log Files) (0) | 2021.09.02 |
백준 알고리즘 파이썬(Python) 14501번 퇴사 (0) | 2021.08.30 |
백준 알고리즘 파이썬(Python) 10972번 다음 순열 (0) | 2021.08.25 |
백준 알고리즘 파이썬(Python) 9095번 1, 2, 3 더하기 (0) | 2021.08.24 |