문제

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

팰린드롬(Palindrome): 앞뒤가 똑같은 단어나 문장, 뒤집어도 같은 말이 되는 단어 또는 문장을 팰린드롬이라고 한다.

예제1

• 입력

"A man, a plan, a canal: Panama"

• 출력

true

예제2

• 입력

"race a car"

• 출력

false

나의 풀이

이 문제는 대소문자를 구분하지 않고, 영문자와 숫자만을 대상으로 한다.
그래서 첫 번째로 주어진 문자열에서 숫자일 때와 영문자일때 새로운 리스트에 담는다. 영문 대소문자는 구분하지 않으므로 소문자로 변경한다.
다음은 팰린드롬인지 확인하기 위해 원래 문자열과 그것을 뒤집은 문자열을 비교한다. 팰린드롬이면 True를 리턴하고 아니면 False를 리턴한다.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 나의 풀이
        answer = False
        s = list(s)
        only_char = []
        
        # 숫자와 문자만 뽑아서 새로운 리스트에 저장
        for i in s:
            if i.isdigit():
                only_char.append(i)
            if i.isalpha():
                only_char.append(i.lower())
        
        # origin = 원형
        # reverse_origin = 원형을 뒤집은 것(슬라이싱 사용)
        origin = only_char
        reverse_origin = only_char[::-1]

        if origin == reverse_origin:
            answer = True

        return answer

이렇게 문제를 풀어보았고 풀이법 3가지를 더 알게 되어서 공유하려고 한다.

풀이1 - 리스트로 변환

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 풀이1 리스트로 변환
        s = list(s)
        only_char = []
        for i in s:
            # 알파벳과 숫자일때
            if i.isalnum():
                only_char.append(i.lower())
                
	# 문자열 앞과 끝을 동시에 pop 하면서 비교한다
        while len(only_char) > 1:
            if only_char.pop(0) != only_char.pop():
                return False

        return True

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

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 풀이2 데크 자료형 이용 -> 최적화
        # 자료형 데크로 선언
        strs = collections.deque()

        for char in s:
            if char.isalnum():
                strs.append(char.lower())

        # 데크 자료형의 popleft 함수를 이용한다
        while len(strs) > 1:
            if strs.popleft() != strs.pop():
                return False

        return True

풀이1은 리스트 자료형을 사용했고 풀이2는 데크 자료형을 사용했다. 데크자료형을 사용한 풀이2는 풀이1보다 속도가 빠르게 나오는데 그 이유는 무엇일까?
그 이유는 while문 안에서 자료의 앞과 끝을 비교할때 사용한 pop(0)과 popleft()의 차이 때문이다. 리스트의 pop()은 $O(n)$이고, 데크의 popleft()는 $O(1)$이다.
이처럼 데크 자료형을 적절히 사용한다면 코드의 성능을 조금 더 높일 수 있다.

풀이3 - 슬라이싱 사용

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

이 풀이는 정규식으로 불필요한 문자를 필터링 한 후에 파이썬의 문자열 슬라이싱을 이용했다.


혼자 문제를 풀어보고 다른 풀이들을 보고 데크, 슬라이싱, 정규식 등을 공부하게 됐다.
예전에는 혼자 문제를 해결하면 다른 풀이를 보거나 다른 방식으로 풀어본 경험이 없었다. 여러개의 풀이를 보고 내가 정확히 모르던 파이썬 문법이나 개념들을 알아갈 수 있었다.

출처: 파이썬 알고리즘 인터뷰