LeetCode(125번)

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

---

ex)

# Input
'A man, a plan, a canal: Panama'

# Output
'True'

나의 풀이

class Solution:
    def isPalindrome(self, s: str) -> bool:
    	# 정규화식(특수문자를 걸러준다)
        pattern = '[-=_+,#/\?:;^$.\{\}@*\"※~&%ㆍ!』\\‘|\(\)\[\]\<\>`\'…》]'    # 특수기호제거
        #re의 sub을 이용하여 특수문자 제거
        text = re.sub(pattern=pattern, repl='', string=s)
        
        #공백까지제거하고 모든문자를 소문자로만든다
        origin_text = text.replace(' ', '').lower()
        #거꾸로된 문자를 변수로 만든다
        reverse_text = origin_text[::-1]
        
        #if문으로 비교한다
        if origin_text == reverse_text:
            return True
        else:
            return False

runtime : 52 ms

슬라이싱을 이용한 풀이

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        
        s = re.sub('[^a-z0-9]', '', s)
        
        return s == s[::-1]

runtime : 36 ms

• 코드와 정규식을 조금더 간결하게 만들어서 푼 문제이다.
• if문을 안쓰고 return 에다가 집어넣어도된다는 사실을 깨달았다.

리스트를 이용한 다른 풀이

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

runtime : 300 ms

Deque를 이용한 최적화

class Solution:
    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

runtime : 60 ms

• deque
  • 데크는 스택과 큐를 모두 가진 객체로 출입구를 양쪽에 가지고있다.
  • 스택처럼 써도 되고, 큐처럼 써도된다.
• 리스트의 pop(0)이 O(n)인 데 반해, 데크의 popleft()는 O(1)이기 때문에 성능을 5배 가까이 늘릴 수 있었다. (각각 n번 반복하면 리스트구현은 O(n제곱), 데크 구현은 O(n))

---

책 : 파이썬 알고리즘 인터뷰 - 박상길 내용을 참고하였습니다.