유효 팰린드롬 찾기

Reference{:target="_blank"}

팰린드롬(Palindrome)?

앞뒤 상관없이 순서대로 읽어도 같은 문자열일 경우 팰린드롬(Palindrome)이라고 한다.

ex) 이효리는 거꾸로 읽어도 이효리

문제 조건

오직 알파멧과 숫자만 팰린드롬의 조건으로 사용한다.

어떻게 풀까

문자열의 앞뒤를 참조하는 포인터를 사용하여 값을 비교하며 순회를 한 뒤 문자가 다르다면 False를 리턴한다.

두 포인터가 만나거나 교차할 때까지 문자가 다른 경우가 없다면 팰린드롬이다.

풀이

팰린드롬 조건에 해당되지 않는 공백문자나 특수문자를 제거가 필요하다.

제거한 결과를 담을 공간이 필요한데 일반 list도 괜찮지만 deque을 사용하는 것도 좋다.

deque는 collections에서 제공하는 자료구조이다.

from collections import deque

deq = deque()

# 문자열을 순회해서 필요한 문자와 숫자만 덱에 담는다.
for char in s:
  if char.isalnum():
    deq.append(char.lower()) # 팰린드롬에 대소문자 구별은 없기때문에 모두 소문자로 변환

팰린드롬 확인을 위한 조건이 갖춰졌으므로 이제 비교를 하며 순회하면 해결된다.

while(len(deq) > 1):
  if deq.pop() != deq.popLeft():
    return False

return True

pop을 하면 deque의 길이가 줄어들고 서로 교차하기 직전의 길이는 문자열의 길이가 짝수일 때 0, 홀수일때 1이므로

이때까지 이상이 없다면 팰린드롬의 조건을 만족한다.

다른 풀이

문자열 슬라이싱을 활용해서 풀 수도 있다. 그리고 정규 표현식을 사용해서 조건을 간단하게 해결할 수 있다.

import re # 정규 표현식을 위해 필요한 모듈

s = s.lower()
s = re.sub('[^a-z0-9]', '', s)  # 소문자, 숫자를 제외하곤 모두 제거하는 정규 표현식

return s == s[::-1]