[python3 | 알고리즘] 11. 문자열 조작(팰린드롬)

1. 펠린드롬(Palindrome)인지 체크하기

 

 - 조건 : 대소문자 구분하지 않음, 영문자와 숫자로만으로 구성

 - 사용 함수 

   1) isalnum() : 영문자, 숫자 여부 판별 함수

   2) lower() : 모두 소문자로 바꾸는 함수

 

 

2. 구현 방법

- 리스트 이용
- Deque 이용
- 슬라이싱 이용

 

리스트로 구현

- O(n제곱) 

- 포인트 : pop(0)와 pop() 이 같은가?

 

# list 선언

strs = []

 

 

Deque 자료형 이용

- O(n) : 리스트보다 속도 빠름

- 포인트 : popleft()와 pop() 이 같은가?

 

# deque 선언

strs : Deque = collections.deque()

 

 

슬라이싱 이용

- Deque 보다 속도 빠름. C언어보다는 느림

- 포인트 : 정규식 이용 후 슬라이싱

 

import re

 

# 정규표현식으로 영숫자만으로 걸러냄 

s = re.sub('[^a-z0-9]', '', s)

 

# 슬라이싱 ([::-1] ==> 뒤집기)

# 내부적으로 C로 구현되어 있어서 빠르다.

return s == s{::-1]

 

 

C 언어로 구현

bool isPalindrome(char *s) {
    int bias_left = 0;
    int bias_right = 0;
    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)
            break;
     
        if(tolower(s[i+bias_left] != tolower(s[str_len - i -bias_right]))
            return false;
    }
    return true;
}