01. Valid Palindrome

🎯 leetcode - 125. Valid Palindrome

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 1번 문제
- 주어진 문자열이 팰린드롬(뒤집어도 같은 말이 되는 단어 또는 문장)인지 확인하라. 
- 대소문자를 구분하지 않으며 영문자와 숫자만을 대상으로 판별한다.

📌 날짜

2020.01.14

📌 시도 횟수

1 try

💡 Code

class Solution:
    def palindrome(self, s):
        arr = []
        for char in s:
            if char.isalnum():
                arr.append(char.lower())

        mid = int(len(arr) / 2)
        i = 0
        while len(arr) > mid:
            if arr[i] == arr.pop():
                i += 1
            else:
                return False
        return True

💡 문제 해결 방법

- 주어진 문자열을 2로 나눈 길이를 mid로 설정했다.
- 팰린드롬은 문자열 중앙을 기준으로 대칭적인 위치의 문자가 서로 같다.
- 주어진 문자열의 길이가 mid가 될 때까지 팰린드롬을 검사한다.
- while문을 돌 때마다 i(초기값이 0)는 1씩 커짐으로써 맨 앞의 문자부터 차례대로 접근한다.
- while문을 돌 때마다 해당 문자가 팰린드롬을 만족하면 pop() 해준다. 
(따라서 pop을 통해 while을 돌 때마다 맨 끝의 문자부터 역방향으로 차례대로 접근이 가능하다.)
- while문을 돌 때 마다 arr[i] == arr.pop()을 해주면 대칭적인 위치의 문자를 서로 비교할 수 있다.
- 만약 팰린드롬을 만족하지 못하게 되면 즉시 return False를 통해 프로그램을 종료시킨다.
- while문을 모두 돌고 나오면 해당 문자열은 팰린드롬이 된다. 따라서 return True를 한다.

💡 새롭게 알게 된 점

- isalnum() : 문자열이 영어, 한글 혹은 숫자로 되어있으면 참을 , 아니면 거짓을 리턴한다.
- string으로 입력 받으면 index를 통해 각각의 문자(char)에 접근할 수 있다. 

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---

😉 다른 풀이

📌 하나. 데크(Deque) 자료형 이용하기

class Solution:
    def palindrome(self, s: str) -> bool:
        arr: Deque = collections.deque()
        for char in s:
            if char.isalnum():
                arr.append(char.lower())

        while len(arr) > 1:
            if arr.popleft() != arr.pop():
                return False
        return True

💡 새롭게 알게 된 점

- list의 pop(0)은 시간복잡도가 O(n)인데 반해, 데크(Deque)의 popleft()는 O(1)이다. 
- Deque를 사용하기 위해서는 import collections를 한다.
- 사용할 때는 strs : Deque = collections.deque()와 같이 사용할 수 있다.

---

📌 둘. 슬라이싱 사용하기

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        s = re.sub('[^a-z0-9]', '', s)
        return s == s[::-1] # s[::-1] → 문자열을 뒤집는다.

💡 새롭게 알게 된 점

- 파이썬에서 문자열을 조작할 때는 항상 슬라이싱을 우선으로 사용하는 편이 속도 개선에 유리하다.
- 파이썬의 경우 별도 자료형으로 매핑하는 과정에서 상당한 연산 비용이 필요하다.
- 정규표현식(re)을 사용하여 문자열 전체를 한번에 영숫자만 걸러내도록 처리할 수 있다.
- 문자열을 [::-1]으로 처리하면 뒤집을 수 있다.
- 슬라이싱을 이용한 회문 처리가 제시된 방법 중 가장 빠르다.

참고 : 파이썬 정규표현식(re)