(leetcode) Valid Palindrome

주어진 문자열이 팰린드롬 인지 확인. 대소문자를 구분하지 않으며 영문자와 숫자만을 대상으로 한다.

 

- 입력

"A man, a plan, a canal: Panama"

- 출력

True

 

 

 

1. 리스트 자료형 사용

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = []
        for char in s:
            if char.isalnum(): # 문자 또는 숫자일 경우 True
                strs.append(char.lower())
                
        while len(strs) > 1:
            if strs.pop(0) != strs.pop():
                return False
        
        return True

 

 

2. 덱 자료구조를 사용한 최적화

import collections

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.pop() != strs.popleft():
                return False
        
        return True

leetcode에서 직접 실행해본 결과 리스트 자료형에 비해 약 2배 가까이 빨랐다. 리스트의 pop(0)은 O(n) 이고 덱의 popleft()는 O(1) 이기 때문이다.

 

---

참고 

문자열 슬라이싱 

 

 0  1  2  3  4

안 녕 하 세 요

-5 -4 -3 -2 -1 

 

• s[1:4] == 녕하세
• s[1:-2] == 녕하
• s[:] == 안녕하세요 : 값 복사를 의미
• s[::1] == 안녕하세요 : 1은 기본값으로 동일
• s[::-1] == 요세하녕안 : reverse
• s[::2] == 안하요 : 2칸씩 앞으로 이동