6장_1 문자열 조작(유용한 펠린드롬)

팰린드롬이란 앞으로 읽어도 뒤로 읽어도 같은 문자의 순서가 되는 단어 또는 문장이다.
우리말로는 '회문'이라고 하며 대표적인 문장으로는 '소주 만 병만 주소'와 같은 문장이 이에 해당된다.
지금 사용할 펠린드롬은 "A man, a plan, a canal: Panama"이다.

1. 리스트로 변환

//문자열저장, 변환
class Solution:
    def isPalindrome(self, s: str) -> bool:
        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

리스트로 변환하는 방법은 strs에 문자들을 하나씩 저장하는데 isalnum은 영문, 숫자만 읽는 명령이다. 그리고 대소문자를 구분하지 말아야 하니까 lower를 사용하여 소문자로 변환한다.

그러면 다음과 같은 값들이 리스트에 저장된다.
['a', 'm', 'a', 'n', 'a', 'p', 'l', 'a', 'n', 'a', 'c', 'a', 'n', 'a', 'l', 'p', 'a', 'n', 'a', 'm', 'a']

저장한 펠린드롬을 pop을 사용하여 맨앞의 단어와 맨 뒤의 단어와 비교한다. 비교한 단어는 리스트에서 빠져나온다. 그리고 다시 맨 앞과 맨뒤의 단어를 비교한다.
pop(0)으로 맨 앞의 문자와 pop()으로 맨 뒤의 단어와 비교하여 일치하지 않으면 False를 일치하면 True를 반환한다.

이 방법은 런타임이 비교적 길게 나온다 다른 방법을 써보자.

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

class Solution:
    def isPalindrome(self, s: str) -> bool:
        #자료형 데크로 선언
        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

pop의 연산은 단방향이다. 그에 반해 데크는 Head와 Tail간의 양방향 연산이 가능하다.

strs: Deque = collections.deque()와 같이 자료형을 데크로 선언하는 것만으로도 런타임이 많이 감소된다.

이유는 pop(0)이 O(n)인 데 반해, 데크의 popleft()는 O(1)이기 때문이다. 각각 n번씩 반복하면 O(n제곱)과 O(n)으로 차이가 꽤 크다. 이정도면 나쁘지 않은 결과인 것 같다. 하지만 파이썬의 최적화된 내부 기능을 잘 활용해 성능을 좀 더 높여보자.

3. 슬라이싱 사용

import re

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

여기서는 알고리즘이라 할 것이 없다.
정규식으로 불필요한 문자를 필터링하고 문자열을 조작할 수 있는 파이썬의 슬라이싱을 사용했다.

슬라이싱: 위치를 지정하면 해당 위치의 배열 포인터를 얻게 되며 이를 통해 연결된 객체를 찾아 실제 앖을 찾아내는데, 이 과정은 매우 빠르게 진행된다.

먼저 문자열을 모두 소문자로 변경한다.

s = re.sub('[^a-z0-9]', '', s)의 뜻은 s = re.sub의 sub는 subsitute로 대체품이란 뜻을 가진 단어로 문자열을 원하는 것으로 변경한다. 무엇을? [^a-z0-9]의 앞에 ^ 가 붙었다. 그렇다면 [^a-z0-9]는 [a-z0-9]가 아닌 경우가 된다.
[a-z0-9]가 아닌 경우에 대한 것을 '공백'(삭제)으로 바꾸겠다.

이렇게 변경한 것을 슬라이싱을 사용하여 s == s[::-1]로 비교해 맞다면 Ture 아니면 False를 반환한다.

데크도 빨랐지만 슬라이싱을 사용하여 더욱 빨라진 결과를 보여준다.

앞의 풀이는 isalnum을 사용하여 모든 문자를 일일히 점검하였지만 여기선 문자열 전체를 영숫자만 걸러내도록 정규식으로 처리했다. 파이썬은 문자열을 배열이나 리스트처럼 자유롭게 슬라이싱할 수 있는 좋은 기능을 제공하며 [::-1]을 이용하면 뒤집을 수있다.

번외4. c구현

bool isPalindrome(char * s){
    int bias_left = 0;
    int bias_right = 1;
    
    int str_len = strlen(s);
    for(int i = 0; i < str_len; i++) {
        //스킵 포인터 처리
        while (!isalnum(s[i + bias_left])) {
            bias_left++;
            if (i + bias_left == str_len)
                return true;
        }
        
        while (!isalnum(s[str_len - i - bias_right])) {
            bias_right++;
        }
        
        if (i + bias_left >= str_len - i -bias_right)
            break;
        
        //팰린드롬 비교
        if (tolower(s[i + bias_left]) !=  tolower(s[str_len - i - bias_right]))
            return false;
    }
    return true;
}

최고의 속도를 내기 위해 c언어로 구현했다. 문자열을 저장하는 char포인터에 대한 직접 조작으로 가능한 빠르게 동작하도록 작성했다.

int str_len = strlen(s);
for(int i = 0; i < str_len; i++) {
//스킵 포인터 처리
while (!isalnum(s[i + bias_left])) {
bias_left++;
if (i + bias_left == str_len)
return true;
}

문자열을 증가시켜 가면서 bias_left 가 문자열의 길이까지 도달하면 true를 반환하는데 그 다음에 올 코드도 같이 봐야한다.

while (!isalnum(s[str_len - i - bias_right])) {
bias_right++;

오른쪽부터 진행하는데 문자열이나 숫자가 아니라면 증가시켜 건너뛴다는 의미이다.

if (i + bias_left >= str_len - i -bias_right)
break;

왼쪽으로 진행을 하다가 오른쪽에서도 진행하는 것과 만나 지나쳐 i + bias_left가 커지게 되면 멈춘다는 의미이다.

//팰린드롬 비교
if (tolower(s[i + bias_left]) != tolower(s[str_len - i - bias_right]))
return false;

그리고 마지막으로 팰린드롬을 비교하여 왼쪽과 오른쪽을 비교하여 다르면 False 맞으면 true를 반환하고 끝난다.

모든 기능을 직접 처리해야하니 코드는 길어졌지만 위치 포인터를 직접 조작하기 때문에 속도는 매우 빨라진다.
실행해보면 4ms라는 매우 빠른 속도를 보여준다.