[ Leetcode ] 125번 Valid Palindrome 풀이

 

이 포스팅은 "파이썬 알고리즘 인터뷰" 를 읽고 작성된 포스팅임을 밝힙니다.

 

 

 

leetcode.com/problems/valid-palindrome/

Valid Palindrome - LeetCode

 

 

 

 

 

 

 

펠린드롬이란?

 

 

앞뒤가 같은 단어나 문장을 말하는 것으로,

 

"수박은 박수" 나 "다시 합창합시다" 와 같은 것을 말한다.

 

 

해당 문제는 대소문자를 구분하지 않은 영문자와 숫자를 대상으로

펠린드롬인지 아닌지에 대한 여부를 판단하는 문제이다.

 

 

 

 

 

List 로 풀기

 

 

 

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 : 288ms

 

 

데크 자료형을 이용해 풀기

 

 

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs: Deque = collections.deque()
            
        for char in s:
            if char.isalnum():
                strs.appned(char.lower())
                
        while len(strs)> 1:
            if strs.popleft() != strs.pop():
                return False
        return True

 

 

Runtime : 56ms

 

 

 

리스트로 구현한 코드에서 pop(0) 에 해당하는 빅오는 O(n) 이지만,

데크 자료형에서의 popleft() 는 O(1) 이기 때문에, 이렇게 Runtime 차이가 난다.

 

 

 

 

 

슬라이싱을 이용해서 풀기

 

 

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

 

 

진짜 문자열 슬라이싱은 사기다.

 

Runtime : 40ms

 

 

 

슬라이싱을 이용할 때,

우리가 위치를 지정해주면 해당 위치를 가진 배열의 포인터를 얻게 된다.

이를 통해 연결된 객체를 찾아 실제 값을 찾아내는 것이다.

 

이 과정은 속도가 굉장히 빨라서 문자열을 조작할 때면

슬라이싱을 사용하는 것을 권장한다.

 

 

 

 

 

 

 

오늘도 즐거운 파이썬 ~