[파이썬 알고리즘 인터뷰]6장_문자열 조작 01_유효한 펠린드롬(파이썬 isalnum(), lower(), re.sub()으로 문자열에서 특정문자 제거 ,deque 자료형, 슬라이싱 사용,pop(0)과 popleft의 시간복잡도)

#이 포스팅에서 암기해야할 점

1. pop(0)의 시간복잡도는 O(N), 데크의 popleft()는 시간복잡도는 O(1), 둘의 기능은 같음! 

2. s.isalnum() 숫자나 문자일때만 true리턴 

3. s.lower() 소문자로 바꿔서 리턴

4. 데크 사용법 from collections import deque → deque=deque()

5. 슬라이싱 사용법 s[:],s[::2],s[::-1],s[-1] 등등등...

6. 정규식으로 문자 외에 것 제거하기 s=re.sub('[^a-z0-9]','',s) #a~z, 0~9 를 제외한(^) 나머지는 ''로 치환해서 s에 담아라 

#책 페이지

p.138

#문제 링크

Loading... (leetcode.com)

Valid Palindrome - LeetCode

#문제

Given a string s, determine if it is a palindrome, 
considering only alphanumeric characters and ignoring cases.

 
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.
 

Constraints:

1 <= s.length <= 2 * 105
s consists only of printable ASCII characters.

#풀이1_리스트로 변환

class Solution(object):
    def isPalindrome(self, s):
        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

▲설명
isalnum() : 문자열이 영어, 한글, 숫자로 이루어져 있으면 참을 리턴한다.

lower() : 문자를 모두 소문자로 만들어서 리턴한다.

단, pop(0)의 시간복잡도는 O(N)이어서 이 풀이의 시간복잡도의 경우 O(N^2)이 된다. 

#풀이2. 데크 자료형을 이용한 최적화

class Solution(object):
    from collections import deque
    def isPalindrome(self, s):
        #자료형을 데크로 선언
        strs = deque()
        
        for char in s : #s가 "abcba라면" char = a,b,c,b,a
            if char.isalnum() :
                strs.append(char.lower()) #strs = [a,b,c,b,a]
        
        while len(strs) > 1 : #strs의 길이는 현재 5이고 1보다 클때까지이므로 4번 돈다.
            if strs.popleft() != strs.pop() :
                return False #하나라도 다르다면 
        
        return True #다 돌고 나왔다면 True

▲데크 자료형을 이용하여 푼다.

풀이1에서 pop(0)의 시간복잡도가 O(N)이었다면, 풀이2 데크의 popleft()는 시간복잡도가 O(1)이다. 

따라서 이 코드의 시간복잡도는 O(N)이 된다. 

#풀이3. re.sub()과 정규식으로 불필요한 문자 제거 & 슬라이싱으로 풀기 

class Solution(object):
    def isPalindrome(self, s):
        
        #모두 소문자로 바꾸기 
        s=s.lower() #s="ABCBA라면" s="abcba"로 변환된다. 
        
        #re.sub(), 정규식으로 불필요한 문자 필터링
        s = re.sub('[^a-z0-9]','',s)
        
    
        return s == s[::-1] #슬라이싱 s="abcba"와 s[::-1]="abcba"를 비교해서 같으면 펠린드롬임!

▲슬라이싱을 사용하여 푼다.

이때 s[::-1]은 s를 꺼꾸로 돌려준다.

ex) 만약 s가 abcde라면 s[::-1]은 edcba가 된다.

 

→풀이2에 비해 약 2배 정도 더 속도를 높일 수 있다. 

#문자열 슬라이싱 특징

파이썬에서는 '문자열 슬라이싱'이라는 매우 편리한 기능을 제공한다. 무엇보다도 내부적으로 매우 빠르게 동작한다.

위치를 지정하면 해당 위치의 배열 포인터를 얻게 되며 이를 통해 연결된 객체를 찾아 실제 값을 찾아내는데 이 과정을 매우 빠르게 진행되므로 문자열을 조작할 때는 항상 슬라이싱을 우선으로 사용하는 편이 속도 개선에 유리하다. 

문자열을 별도 자료형으로 매핑하는 과정에서 상당한 연산 비용이 필요하므로 전체적인 속도에서는 오히려 손해를 볼 수 있다. 대부분의 문자열 작업은 슬라이싱으로 처리하는 편이 가장 빠르다!!

 

※슬라이싱을 기준으로 한 파이썬 문자열 처리 실행 시간

슬라이싱 < 리스트 reverse() < reversed() + join() < for반복 < while 반복 < 재귀 

▲슬라이싱이 가장 빠르고 재귀가 가장 느림을 알 수 있다.

 

※슬라이싱 사용방법 숙지하기

s="안녕하세요" 

0	1	2	3	4
안	녕	하	세	요
-5	-4	-3	-2	-1

s[1:4] == 녕하세

s[1:-2] == 녕하

s[1:] == 녕하세요

s[:] == 안녕하세요

s[1:100]==녕하세요

s[-1] == 요

s[:-3] == 안녕

s[-3:] == 하세요 

s[::1] == 안녕하세요

s[::-1] == 요세하녕안

s[::2] == 안하요 

▲여기서 알아둬야할 점!

둘 다 생략하면 사본을 리턴한다. 파이선은 a=b와 같은 형태로 할당하면 변수의 값이 할당되는 것이 아니라 a변수가 b변수를 참조하는 형태가 된다. 참조가 아닌 값을 복사하기 위해 [:]를 사용할 수 있다. 이 방식은 문자열이나 리스트를 복사하는 파이썬 다운 방식이기도 하다.