Pallindrome 문제

 Pallindrome은 앞뒤가 똑같은 단어다. 회문이라고도 한다. 주어진 글자가 팰린드롬인지 확인하는 파이썬 코드를 작성하자. 

오직, 영어 소문자 그리고 숫자만으로 고려한다고 가정한다.

이번 시간에는 3.7 버전의 파이썬에 추가된 타입 힌트(type hint) 기능을 사용한다.

타입 힌트란?

파이썬 데이터에 int, float, str, bool 등의 데이터 타입을 빠르게 유추할 수 있도록 도와준다.

풀이

def isPallindromeByList(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

일반적인 리스트(list)를 이용한 풀이다. 우선 strs=[]로 리스트를 정의했다. 함수 isPallindromeByList()는 s라는 이름으로 파라미터를 입력받는다. 이때 타입 힌트로 str을 줬다. 해당 함수는 bool로 return 될 것임을 타입 힌트로 할당했다(->). 이제 strs를 어떻게 다루는지 보자.

먼저 입력값 s가 문자다. 문자는 list로 처리되므로 각 문자를 처음부터 뽑아 char로 저장하고 살펴본다. 이때 char.lower()로 문자를 모두 소문자로 처리한다. 그리고 strs에 하나씩 붙여 넣자. 각 문자가 strs에 한 자씩 들어간다.

다음이 진짜다. strs의 문자가 하나도 남지 않을 때까지 앞에서부터 뽑아낸다. list의 pop()에 아무런 입력이 없으면 맨 뒤의 것을 뽑는다. 그런데 pop(0)이면 제일 앞의 것을 뽑는다. pop(0) != pop()이면 제일 뒤와 앞이 서로 다른 것이므로 회문이 아니다. 단 하나라도 이런 경우가 있으면 팰린드롬 문제에서 False를 받아야 한다. 따라서 그냥 발견되면 return False로 함수가 종료된다. 끈질긴 테스트에서도 아무런 문제가 없다면 while은 종료되고 return True로 회문임이 증명된다.

결과를 돌려보면 다음과 같다.

> test="A man, a plan, a canal: Panama"

> isPallindromeByList(test)

True

다른 풀이들:

이외에도 deque를 이용하는 방법과 순서를 뒤집어 비교하는 방법 등 다양한 알고리즘이 존재한다. 자기만의 알고리즘을 생각해보자.

import collections

import re

def isPallindromeByDeque(s:str) -> bool:

  strs:Deque=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

def isPallindromeBySlice(s:str)->bool:

  s=s.lower()

  s=re.sub('[^a-z0-9]','',s)

  return s==s[::-1]

결과를 보자.

> isPallindromeByDeque(test)

True

> isPallindromeBySlice(test)

True