[파이썬 알고리즘 인터뷰] 1. 유효한 팰린드롬 (leetcode 125)

 

이 글은 파이썬 알고리즘 인터뷰를 공부하며 작성한 글입니다

---

leetcode 125. Valid Palindrome

Valid Palindrome - LeetCode

문제

 

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

 

팰린드롬 : 앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장

 

 

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

 

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

 

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

 

내 풀이

class Solution:
    def isPalindrome(self, s: str) -> bool:
        a = ""
        for i in s:
            if i.isalnum():
                a += i.upper()
        return a == a[::-1]

 

딱 이 문제를 처음 봤을 때 저번에 파이썬 공부하면서 썼던

 

이 부분이 생각이 났다. 문자나 숫자나 영어나 각각에 따라 적용할 수 있는 함수들이 따로 있었는데.. 라는 생각이 들었고, 이 문제를 만족하려면 isalnum을 쓰면 좋겠다는 생각을 했다. (참고)

[파이썬][문제] map(int, input().strip().split(' '))

 

그래서 처음에 리스트를 쓸까도 생각을 했지만 문자열을 이용하기로 했고, 문자열을 넣고 그거 뒤집어서 한거랑 똑같으면 true, 아니면 false를 출력하도록 코드를 구현하였다.

 

+ [::-1]을 이용하였고, 리스트, 튜플, 문자열에서는 이렇게 할 수 있다.

 

 

 

 

 

---

 

책 풀이1 - 리스트로 변환

 

직접 문자열을 입력받아 팰린드롬 여부 판별

isalnum() : 영문자, 숫자 여부를 판별하는 함수로, 이를 이용해 해당하는 문자만 추가

pop()을 통해 맨 앞과 맨 뒤 값이 같은지 확인하는 식으로 접근

def isPalindrome(self, s: str) -> bool: 
	str = [] 
    for char in s: 
    	if char.isalnum(): 
        	str.append(char.lower()) 
        
    # 팰린드롬 여부 판별
    while len(str) > 1: 
        if str.pop(0) != str.pop(): 
            return False 
    return True

 

책 풀이2 - 데크 자료형을 이용한 최적화

 

Deque(데크) 

strs : Deque = collections.deque()

양쪽 끝 모두 접근가능하여 양 끝 연산에 대한 복잡도가 list에 비해 대폭 상승함. 

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

 

책 풀이3 - 슬라이싱 사용

 

정규식과 [::-1] 이용

def isPalindrome(self, s: str) -> bool: 
    s=s.lower() 
    s=re.sub('[^a-z0-9]','',s) 
    
    return s==s[::-1] #슬라이싱

 

 

 

<참고>

책 : 파이썬 알고리즘 인터뷰

책 풀이 코드 출처

GitHub - onlybooks/python-algorithm-interview: <파이썬 알고리즘 인터뷰> 95가지 알고리즘 문제 풀이로 완성

 

기타 개념 참고

파이썬 자료구조 - 큐 Queue 와 데큐 Deque

[Python] 파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O)

 

덱 - Deque (Double ended Queue)