팰린드롬 구별(Deque, Slicing)

팰린드롬(Pelindrome)이란?

 

앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장을 팰린드롬이라 합니다. 우리 말로는 "소주 만 병만 주소" 같은 문장을 일컫습니다.

 

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

 

먼저 해당 문제의 솔루션을 리스트를 사용하여 구현하고, 성능 개선을 위해 Deque 자료형과 문자열 슬라이싱을 사용해 코드를 작성해보도록 하겠습니다!

 

 

리스트로 반환

 

영문자, 숫자 여부를 판별하는 isalnum() 함수를 사용하여 문자열 리스트에 대입한 후, 첫 번째 문자와 마지막 문자를 pop() 함수를 통해 비교해나가는 방식입니다.

def isPalindrome(s: str) -> bool :
    strs = []
    for char in s:
        # return True when string is composed of Character or Number
        if char.isalnum():
            strs.append(char.lower())

    # differentiate palindrome
    while len(strs) > 1:
        if strs.pop(0) != strs.pop():
            return False

    return True

 

하지만 위 방식은 리스트의 pop(0)이 O(n)이므로 각각 n번씩 반복하면입니다. 성능 개선을 위해 Deque 자료형을 활용하도록 하겠습니다.

 

Deque 자료형을 이용한 최적화

 

deque의 popleft()는 O(1)이기 때문에, Deque 자료형을 사용하여 구현하는 방식은 리스트를 사용하여 구현했을 때인 O(n^2)보다 개선된 O(n)의 선형복잡도를 가집니다. 

import collections
from typing import Deque

def isPalindrome(s: str) -> bool:
    # declare deque
    strs: Deque = collections.deque()

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

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

    return True

 

문자열 슬라이싱을 활용한 실행시간 개선

 

isalnum() 함수를 사용하여 모든 문자를 일일이 검사했던 이전 방식들과는 다르게 정규표현식으로 불필요한 문자열을 필터링하고, 문자열을 조작할 수 있는 파이썬의 Slicing을 사용한 방식입니다.

 

파이썬은 문자열을 배열이나 리스트처럼 자유롭게 슬라이싱할 수 있는 좋은 기능을 제공합니다. 이를 사용하여 코드 길이를 줄일 수 있고, 내부적으로 C로 구현되어 있어 훨씬 더 좋은 속도를 기대할 수 있습니다.

def isPalindrome(s: str) -> bool:
    s = s.lower()
    
    # s 문자열에서 a부터 z, 0부터 9 이외의 문자는 ''으로 대체하는 정규표현식 사용
    s = re.sub('[^a-z0-9]', '', s)
    
    # Extended Slices을 통해 문자열/배열의 인덱스에 접근
    return s == s[::-1]

 

마지막에 s와 s[::-1]을 비교하여 같을 경우 True를, 다를 경우 False를 반환하였는데요. 무슨 의미일까요?

 

Python은 Extended Slices 라는 방식을 사용하여 문자열이나 배열의 인덱스에 접근할 수 있습니다.

 

arr[A:B:C]의 의미는 다음과 같습니다.

→ index A부터 index B까지 C의 간격으로 배열/문자열을 구성해라

 

[::-1]에서는 C의 값이 -1이므로 처음부터 끝까지 -1칸 간격으로, 즉 역순으로 표현하라라는 의미입니다.

C의 값이 -2인 경우에는 처음부터 끝까지 2개씩 역순으로 반환하므로, c = 'ABCDEF' 일 때 c[::-2]란 'FDB'를 반환하는 것입니다.

 

즉, s == s[::-1]은 s와 이 s를 역순으로 표현한 문자열이 동일한지 확인합니다.

 

자료 출처

 

https://docs.python.org/release/2.3.5/whatsnew/section-slices.html

15 Extended Slices

 

도서: 파이썬 알고리즘 인터뷰