목차

• 유효한 팰린드롬
  • 문제
• ‘팰린드롬’ 이란?
• 풀이과정
  • 1. 전처리
  • 2. 팰린드롬 판별
  • PLUS) 데크 자료형을 이용한 최적화
• 전체 코드

👀, 🤷‍♀️ , 📜
이 아이콘들을 누르시면 코드, 개념 부가 설명을 보실 수 있습니다:)

유효한 팰린드롬

난이도 | ★

문제

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
#Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
#Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
#Explanation: s is an empty string "" after removing non-alphanumeric characters.
#Since an empty string reads the same forward and backward, it is a palindrome.

[전제]

* 1 <= s.length <= 2 * 105
* s consists only of printable ASCII characters.

‘팰린드롬’ 이란?

앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장이다.

우리 말로는 ‘회문’이라고 부른다.

예를 들어,
race a car를 보자. 이 문장에 띄어쓰기를 없애면 raceacar이다.

이 문장은 뒤집어도 race a car이다.

이러한 팰린드롬의 특징을 이용하면 많은 문제들을 만들어 낼 수 있기 때문에 코딩 테스트에 자주 출제되기도 한다.

풀이과정

이 문제는 크게 두가지 과정을 거친다.
1️⃣ 전처리: 모두 소문자로 바꾸고 영문자와 숫자만 골라내기
2️⃣ 골라낸 것들의 팰린드롬 판별하기

1. 전처리

먼저 영문자와 숫자만 골라낸 후,
골라낸 것들을 소문자로 바꿔야 한다.

영문자와 숫자와 골라내는 매서드는 바꿀 것.isalnum()이다.
이건 is+alphabet+number라고 기억해두면 좋다.
생각보다 많이 쓰이니까 기억해두자.

그리고 골라낸 것들을 소문자로 바꾸는 매서드는 바꿀 것.lower()이다.

즉 이를 이용하여 코드를 짜보면

def isPalindrome(self, s: str) -> bool:
	str = [] # 소문자인 알파벳과 숫자만 넣을 곳
	for i in s: # 하나하나 둘러보자
	    if i.isalnum(): # 숫자와 골라내는 매서드
		str.append(i.lower()) # 소문자로 바꾸는 매서드

2. 팰린드롬 판별

먼저 넣은 str을 한번씩 봐야된다.
여기에 앞 뒤를 하나씩 꺼내서 보는 것 이다.

앞에 것을 pop(0)을 통해 꺼내고 뒤의 것을 pop()을 통해 꺼낸다.
그리고 이 두개를 비교한다.

그래서 계속 같으면 True 다르면 False를 return하면 된다.

while len(str) > 1:
    if str.pop(0) != str.pop():
	return False
return True

PLUS) 데크 자료형을 이용한 최적화

데크란?

전체 과정을 위와 똑같다

class Solution:
    def isPalindrome(self, s: str) -> bool:
        str: Deque = collections.deque() # 데크선언
        for i in s:
            if i.isalnum():
                str.append(i.lower())
        while len(str) > 1:
            if str.popleft() != str.pop():
                return False
        return True

전체 코드

위를 구현한 전체 코드는 다음과 같다

class Solution:
    def isPalindrome(self, s: str) -> bool:
        str = []
        for i in s:
            if i.isalnum():
                str.append(i.lower())
        while len(str) > 1:
            if str.pop(0) != str.pop():
                return False
        return True