유효한 팰린드롬

📚 유효한 팰린드롬 문제

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

• 입력 : A man, a plan, a canal: Panama

📚 유효한 팰린드롬 문제풀이

💡 팰린드롬? 앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장

💡 풀이1 : 일반 배열을 활용

🗣️ isalnum()은 영문사, 숫자 여부를 판별하는 함수로, 이를 이용해 해당하는 문자만 추가한다.

print('a'.isalnum()) # True 
print('#'.isalnum()) # False

import sys

sentence = sys.stdin.readline().strip()

def isPalindrome(sentence: str) -> bool: 
    str_li = []
   
    for i in sentence :
        if i.isalnum() :
            str_li.append(i.lower())
       
        while len(str_li) > 1 :
            if str_li.pop(0) != str_li.pop() :
                return False

        return True   

• 파이썬 배열은 pop() 함수에서 인덱스를 지정할 수 있기에, 위처럼 0을 지정하면 맨 앞의 값을 가져올 수 있다.
  이렇게 맨 뒷부분의 pop() 결과와 매칭해 일치하지 않을 경우 false를 리턴 모두 통과하면 true를 리턴한다.
• 그러나 위와 같은 풀이의 경우, 실행에 304ms 가 소요됨.

💡 풀이2 : Deque를 활용

import sys
from collections import deque

sentence = sys.stdin.readline().strip()

def isPalindrome(sentence: str) -> bool: 
 	str_li = deque()
   
    for i in sentence :
        if i.isalnum() :
            str_li.append(i.lower())
       
        while len(str_li) > 1 :
            if str_li.popleft() != str_li.pop() :
                return False

        return True   

• deque를 활용한 위 풀이는 64ms가 소요됐다. 이렇게 현저할 정도로 속도차이가 나는 이유는 list에 pop(0)운 O(n)인데 반해 deque의 popleft()는 O(1)이기 때문이다.
• 이를 각각 n 번 반복하면 리스트 구현은 O(n^2), deque 구현은 O(n)으로 성능 차이가 크다. s

💡 풀이3 : 문자열 슬라이싱 사용

🗣️ 정규식 in python
re.sub(pattern, repl, string) -> string에서 pattern에 해당하는 부분을 repl로 대체해주는 함수

• 패턴 : r'[^a-zA-Z0-9]' -> 이 정규식 패턴은 알파벳(a-z, A-Z)과 숫자(0-9)를 제외한 모든 문자를 찾는다. (여기서 ^는 "제외한다"는 의미)

import sys
import re
from collections import deque

sentence = sys.stdin.readline().strip()

def isPalindrome(sentence: str) -> bool: 
 	sentence = s.lower()
    # 정규식으로 문자 필터링
    filtered_sentence = re.sub(r'[^a-zA-Z0-9]', '', sentence)
    // 정규식에 포함되지 않는 글자를 ''(빈칸)으로 대체
   
  	return s == s[::-1] # 슬라이싱

• 이 풀이의 경우, 실행 속도는 36ms로 해당 문제 풀이들 중 가장 빠른 처리 속도를 지녔다.

📚 결론

• 파이썬에서 문자열 슬라이싱은 매우 편리하고, 빠르게 동작한다. 위치를 지정하면 해당 위치의 배열 포인터를 얻게 되며 이를 통해 연결된 객체를 찾아 실제 값을 찾는데, 이 과정은 매우 빠르게 진행되므로 문자열을 조작할 때는 항상 슬라이싱을 우선으로 사용하는 편이 속도 개선에 유리하다.
• 문자열을 별도로 리스트로 매핑하는 처리 방식은, 상당한 연산 비용이 필요하므로 전체적인 속도에서는 오히려 손해를 볼 수 있다.

📚 (참고) 슬라이싱

💡 s = '안녕하세요' 슬라이싱

• S[1:4] == 녕하세 : 인덱스 1에서(0부터 시작) 4 이전까지(4는 포함하지 않는다) 표현한다. 4개를 의미하는 게 아니므로 유의해야 한다.
• S[1:-2] = 녕하: 인덱스 1에서 -2 이전까지(-2는 포함하지 않는다) 표현한다. 그림 6-1에서오 같이 뒤에서부터는 음수로 접근이 가능하다.
• S[1:] == 녕하세요 : 문자열의 시작 또는 끝은 생략 가능하다.
• S[:]== 안녕하세요 : 둘 다 생략하면 사본을 리턴한다. 파이썬은 a = b와 같은 형태로 할당하면 변수의 값이 할당되는 것이 아니라 a 변수가 b 변수를 참조하는 형태가 된다(117페이지 'C++ 참 조와 비교' 참고), 참조가 아닌 값을 복사하기 위해 [:]를 사용할 수 있으며, 이 방식은 문자열 나 리스트를 복사하는 파이썬다운 방식(Pythonic Way)이기도 하다.
• S[1:100] == 녕하세요: 인덱스가 지나치게 클 경우 문자열의 최대 길이만큼만 표현된다. S[1:]과 동일하다.
• S[-1] == 요 : 마지막 문자(뒤에서 첫 번째)
• S[-4] == 녕 : 뒤에서 4번째
• S[:-3] == 안녕 : 뒤에서 3개 글자 앞까지
• S[-3:] == 하세요 : 뒤에서 3번째 문자에서 마지막까지
• S[::1] == 안녕하세요 : 1은 기본값으로 동일하다.
• S[::-1] == 요세하녕안 : 뒤집는다.
• S[::2] == 안하요 : 2칸씩 앞으로 이동한다