[알고리즘][문자열 조작] - 1. 유효한 팰린드롬

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님'을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/valid-palindrome

---

[유효한 팰린드롬]

[팬린드롬이란?]

회문 또는 팰린드롬은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다.
출처: https://ko.wikipedia.org/wiki/%ED%9A%8C%EB%AC%B8 

 

 

[일반 리스트를 사용한 방법]

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

• isalnum( )은 영어, 숫자인지를 판별해주는 함수이다.
• lower( )은 입력 받은 문자가 전부 소문자로 바꿔주는 함수이다. 

 

 

 

[deque 자료형을 이용한 최적화]

from collections import deque

class Solution:
    def isPalindrome(self, s: str) -> bool:
        lst = deque()
        for i in s:
            if i.isalnum():
                lst.append(i.lower())
        # 팰린드롬 여부 판별
        while len(lst) > 1:
            if lst.popleft() != lst.pop():
                return False
        return True

• pop(0)보다 popleft( )가 훨씬 빠르게 작동한다. 그렇기 때문에 맨 앞의 요소를 꺼내서 빈칸을 위해 맨 앞의 바로 뒤 요소를 다 옮겨야 되는 pop이 아닌 popleft( )를 사용하도록 하자
• deque는 스택처럼 쓸 수도 있고, 큐처럼 사용도 가능하다.

 

 

[슬라이싱을 사용한 방법]

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        
        #정규식을 사용한 불필요한 문자 필터링
        s = re.sub('[^a-z0-9]','',s)
        
        return s == s[::-1] #슬라이싱

• s = s.lower() - 문자열을 소문자로 만들어준다.
• s = re.sub('[^a-z0-9]','',s) - 정규식을 사용해 영문, 숫자만 남긴다.
• s == s[::-1] - 남긴 문자와 s[::-1] 뒤집은 문자가 같은지를 비교 연산자를 통해 확인하고 돌려준다.

 

 

[실행 속도 비교]

위에서부터 슬라이싱, 데크 자료형 이용, 리스트 이용 해서 푼 경우다. 

어떻게 알고리즘을 구성하느냐에 따라서 Runtime이 몇배씩 차이가 나는 걸 볼 수 있다.

 

 

[참고 C언어]

C언어로 이 문제를 풀었다면 포인터를 직접 조작하는 방식으로 진행해서 매우 짧은 시간에 이를 해결한다.

파이썬은 인터프리터 언어로 컴파일 언어인 C보다 성능이 조금 더 떨어지는 걸 알수 있다.