[6.문자열조작]유효한 팰린드롬

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

팰린드롬이란?
앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장
우리말로는 '회문'이라 부른다 

예제1

# 입력
"A man, A plan, A canal: Panama"

# 출력
true

 

예제2

# 입력
race a car

# 출력
false

 

개인 풀이

text = str(input())

text = text.lower().replace(",", "").replace(":", "").replace(" ", "")

if list(text) == list(reversed(text)):
    print(True)
else:
	print(False)

 

풀이1. 리스트로 변환

- "string".isalnum() : 영문자, 숫자 여부를 판별하는 함수
- 속도: 304밀리초

def isPalindrome(s: str):
    strs = []
    for char in s:
        if char.isalnum():
            strs.append(char.lower())

    while len(strs) > 1:
        if strs.pop(0) != strs.pop(): # pop은 가장 마지막 값을 꺼내기 때문에,
            return False              # index를 0으로 지정하여
                                      # 가장 앞의 값과 마지막 값을 비교
    return True


text = str(input())
print(isPalindrome(text))

 

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

- 풀이1의 리스트 pop(0)이 O(n)인데 반해, 데크의 popleft()는 O(1)이기 때문에, 각각 n번씩 반복하면 
   리스트 구현은 O(n²), 데크 구현은O(n)으로 성능 차이가 크다. 
- 시간복잡도 이해하기
- 속도: 64밀리초(풀이1의 5배)

import collections

def isPalindrome(s: str):
    strs = 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


text = str(input())
print(isPalindrome(text))

 

풀이3. 슬라이싱 사용

- 정규식으로 불필요한 문자 필터링
- 코드가 훨씬 줄어들고, 내부적으로 C로 빠르게 구현되어 있어 훨씬 좋은 속도를 기대할 수 있다. 
- 속도: 35밀리초(풀이2의 2배)

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


text = str(input())
print(isPalindrome(text))

 

풀이4. C 구현

- 최고 속도 구현/
- 문자열을 저장하는 char 포인터에 대한 직접 조작
- 필터링 해야 하는 문자는  bias_left, bias_right 변수를 이용해 한 칸씩 건너뛰는 형태
- 코드는 길어지지만, 위치 포인터를 직접 조작하기 때문에 매우 빠르게 실행
- 속도: 4밀리초

bool isPalindrome(char *s){
	int bias_left = 0;
    itn 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;
        
 }

 

표 6-1. 슬라이싱을 기준으로 한 파이선 문자열 처리 실행 시간

알고리즘	실행시간	슬라이싱을 1로 했을 때의 비율
슬라이싱	0.499마이크로초	1
리스트 reverse()	2.46마이크로초	5
reversed() + join()	2.49마이크로초	6
for	5.5마이크로초	12
while	9.4마이크로초	21
재귀	24.3마이크로초	54