[leetCode] Valid Palindrome (Python)

✏️ 문제

Valid Palindrome - LeetCode

✏️ 풀이

기본적으로 깔린 생각은 문자/숫자 아닌 거 만나면 만날때까지 pop하다가 만나면 비교하기..

기본 아이디어 자체는 쉬운데 코드로 옮기려니 영 불편했다.

일단 Alphanumeric 체크는 아스키코드 값 비교로 처리했다.

그리고 맨 처음엔 기존 배열을 뒤집은 새로운 배열을 이용해서 두 배열을 앞부터 차례로 비교해나가는 방식을 생각했는데,

그것보다는 한 배열에서 앞과 뒤를 동시에 보면서 뒤에서 이미 검사한 것들은 pop() 해나가는게 시간복잡도가 줄어들거라고 생각했다. (배열 길이의 반 이하만 탐색하면 되니까)

✏️ 코드

class Solution:
    def isPalindrome(self, s: str) -> bool:
        answer = True        
        s = list(s.lower())
        
        for char in s:
            #Considering Only Alphabets and Numbers
            if (char>='0' and char<='9') or (char>='a' and char<='z'):
                pop = 0
                while True:
                    pop = s.pop()
                    if (pop >='0' and pop<='9') or (pop>='a' and pop<='z'):
                        break
                if pop!=char:
                    answer = False
                    break
        
        return answer

풀고나니 같은 조건을 두 번이나 중복해서 검사한다는 게 마음에 들지 않았어서 차라리 처음부터 검사해서 제거하는 게 낫겠다싶다.

✏️ 다른 사람 풀이 (출처 : 파이썬 알고리즘 인터뷰)

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

영문자/숫자를 판별하기 위해서 str.isalnum() 함수를 이용할 수 있다.

이를 이용해서 영문자/숫자만 들어간 새로운 배열을 만들고,

그 이후엔 간편하게 가장 앞/뒤 원소들을 비교해나가면서 각각 pop해준다.

 

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

deque를 사용하면 속도를 더 높일 수 있다.

나머지 알고리즘은 위와 동일한데,

리스트의 pop(0)이 O(n)인 것에 비해 덱의 popleft()는 O(1) 이다.

deque에 관해서 아래 포스팅에 정리하였다.

seonyounggg.tistory.com/95

 

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

        return s == s[::-1]

정규식을 사용한 풀이이다.

문자열 전체를 한번에 걸러내었고, 마지막엔 뒤집은 문자열과 한번에 비교하였다.

정규식은 아예 생각하지 못했는데 마지막 return 문은 충분히 활용할만 한 것 같다.

 

문자열 슬라이싱은 내부적으로 C로 구현되어 있어 매우 빠르게 동작한다.

문자열을 별도의 리스트로 매핑하는 과정에서 상당한 연산 비용을 필요로 하므로 슬라이싱을 우선적으로 사용하는 것이 좋다.

✏️ 생각

데이터 전처리 하는 과정을 시간 낭비라고 생각하지 말자

차라리 전처리를 하고 간단한 알고리즘을 설계한 후에 최적화할 방법을 고민하는게 더 나은 것 같다!