팰린드롬이란?

• 앞뒤가 똑같은 단어나 문장
• ‘기러기’, ‘오디오’
• ‘소주 만 병만 주소’

대소문자를 구분하지 않음
- Level
- Anna

영문자와 숫자만을 대상으로 함

• “A man, a plan, a canal: Panama” → 영문자만 추리면 아래와 같음

• 팰린드롬 맞음

문제에 대한 예시

풀이 1. 리스트로 변환

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

문제풀이에 필요한 개념

String

• isalnum() 메소드
  • Return True if the string is an alpha-numeric string, False otherwise.

  char1 = 'a'
  print(char1.isalnum()) # True
  
  char2 = '5'
  print(char2.isalnum()) # True
  
  char3 = '$'
  print(char3.isalnum()) # False
  

• lower() 메소드
  • 대문자를 소문자로 변환해서 반환

  str1 = 'ABC'
  print(str1.lower()) # abc
  
  str2 = 'AbC'
  print(str2.lower()) # abc
  

List

• pop() 메소드

  lists = ['a', 'b', 'c', 'd']
  
  print(lists.pop()) # d
  
  print(lists) # ['a', 'b', c']
  
  print(lists.pop(0)) # 리스트에서 0번째 인덱스(가장 앞)에 해당하는 'a' 반환
  
  print(lists) # ['b', 'c']
  

• Remove and return item at index (default last).

풀이 2. 데크 자료형을 이용한 최적화

def is_palindrome(s:str)->bool:
		import collections
    strs = 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

• list가 아닌 deque를 이용

if strs.pop(0) != strs.pop(): # strs가 list

if strs.popleft() != strs.pop(): # strs가 deque

• list의 pop(0)의 시간 복잡도는 O() O(n)
  • [0, 1, 2, 3, 4] pop(0) , [None, 1, 2, 3, 4] → [1, 2, 3, 4]
  • [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  • 맨 앞의 element에 pop()을 적용하면 뒤의 요소들을 한칸씩 왼쪽으로 모두 옮겨야 함
• 반면 deque의 popleft() 시간 복잡도는 O(1)
  • 내부적으로 doubly linked list으로 삽입/삭제에 효율이 좋음
  • 1→ 2→ 3→4→5→6, 2만 pop하면 1→3→4→5→6 (뒤는 유지)

풀이 3. 슬라이싱 사용

def is_palindrome_3(s:str) -> bool:
    import re
    s = s.lower()

    s = re.sub('[^a-z0-9]', '', s) # 숫자 문자가 아닌 문자열을 공백으로 변환
    return s==s[::-1]

문제 풀이에 필요한 개념

• 정규식

- [] : 문자 클래스로 [] 사이의 문자들과 매치
- [a-z] : 소문자 알파벳과 매치
- [a-zA-Z] : 알파벳 모두
- [0-9] : 숫자 모두
- [^a-z] : 소문자 알파벳을 제외한 문자와 매치
- [^a-z0-9] : 소문자 알파벳과 숫자를 제외한 문자와 매치

re.sub(first, second, third)

• first : 정규식
• second : first에 매치되는 요소를 second로 치환
• third : 적용될 문자열

str = 'abcABC123!@#'
import re

# 소문자를 공백으로 치환
str_except_small_letter = re.sub('[a-z]', '', str)
print(str_except_small_letter) # ABC123!@#

# 대문자를 공백으로 치환
str_except_big_letter = re.sub('[A-Z]', '', str)
print(str_except_big_letter) # abc123!@#

# 숫자를 공백으로 치환
str_except_numbers = re.sub('[0-9]', '', str)
print(str_except_numbers) # abcABC!@#

# 숫자,문자를 공백으로 치환
str_except_special = re.sub('[a-zA-Z0-9]','', str)
print(str_except_special) # !@#

Reference

1) 책 "파이썬 알고리즘 인터뷰"

2) stackoverflow: deque.popleft() and list.pop(0). Is there performance difference?