[Python]알고리즘 기본 유형 - 유효한 팰린드롬

팰린드롬(회문)이란

---

앞뒤가 똑같은 문장으로 , 뒤집어도 같은 말이 되는 단어 또는 문장을 팰린드롬(Palindrome)이라고 한다. 우리말로는 '회문'이라 부르며, 문장 중에서는 대표적으로 '소주 만 병만 주소'를 예로 들 수 있다.

기본적인 palindrome 유형의 문제는 어떻게 해결하는지 다음의 예제를 통해 알아보자.

주어진 문자열이 팰린드롬인지 확인하여 맞다면 True, 아니라면 False를 출력하라. 단 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.

// 입력 1 : "A man, a plan, a canal: Panama"
// 입력 2 : "race a car"

풀이 1 : 리스트로 변환

---

여기서는 직접 문자열을 입력받아 팰린드롬 여부를 판별해 본다. 이 문제는 대소문자 여부를 구분하지 않으며 영문자, 숫자만을 대상으로 한다는 제약 조건이 있다. 따라서 이 부분을 isalnum()을 이용하여 처리한다. isalnum()은 숫자 여부를 판별하는 함수로, 이를 이용해 해당하는 문자만 추가한다 대소문자를 구분하지 않으므로 lower()로 모두 소문자로 변환한다. 이렇게 하면 입력값이 "A man, a plan, a canal: Panama"일 때 각각의 영문자를 소문자로 변환하여 리스트에 담을 수 있다. 전체 코드는 아래와 같다.

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

풀이 2 : Deque 자료형을 이용한 최적화

---

Deque를 명시적으로 선언하면 문제 해결 속도를 높일 수 있다. 풀이는 아래와 같다.

def isPalindrome(self, s: str) -> bool:
    # 자료형 데크로 선언
    strs: Deque = collections.deque()

    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

풀이 3 : 슬라이싱 사용

---

슬라이싱을 이용하여 문제를 해결할 수도 있다.

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

    # 슬라이싱
    return s == s[::-1]