[Python] 문자열 조작 1 <유효한 팰린드롬>

파이썬 문제 풀이 첫 포스팅이다. 파이썬 같은 인터프리터 언어는 알고림즘의 처리 속도가 Java나 C 보다 느린 것이 단점이지만, 이를 보완하고도 남을만큼 코드를 간단하게 작성할 수 있다는 장점이 있다. Java 프로그래머스 연습 문제 풀이가 얼마 안남았긴 한데, 남은 문제들의 난이도가 상당해서...파이썬과 함께 기초 알고리즘을 먼저 제대로 짚고 넘어가는 것이 더 좋을 거 같다고 생각했다.

 

그럼 가장 기초적이고 빈번하게 나오는 "문자열 조작" 부터 차례차례 문제를 풀어나가도록 하겠다. 

---

<유효한 팰린드롬>

 

팰린드롬은 앞뒤가 똑같은 단어 또는 문장을 말하며, 주어진 문자열이 팰린드롬인지 아닌지 확인하면 되는 문제이다.

앞, 뒤를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.

 

---

알고리즘의 속도에 따라 3가지 방법으로 해당 문제를 풀이할 수 있다.

 

---

1. 리스트를 이용

 

def isPalindromeFirst(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
    
    
if __name__ == '__main__':
    s = "A man, a plan, a canal: Panama"
    s2 = "race a car"
    print(isPalindromeFirst(s))
    print(isPalindromeFirst(s2))

단순하게 리스트를 사용하여 모든 문자를 소문자로 변환하여 삽입한 다음에, 맨 앞 문자와 맨 뒤 문자를 pop하여 비교하여 판별할 수 있다.

---

2. Deque를 이용

 

collections 모듈을 임포트하여 deque로 strs를 선언하면 popleft()를 이용하여 좀 더 빨라진다.

import collections
from typing import Deque

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

if __name__ == '__main__':
    s = "A man, a plan, a canal: Panama"
    s2 = "race a car"
    print(isPalindromeSecond(s))
    print(isPalindromeSecond(s2))

---

3. 슬라이싱

 

파이썬에서는 문자열을 뒤집는 데 아주 편리한 슬라이싱 기능을 하나 가지고 있다.

[::-1]을 이용하면 별 다른 코드 없이 문자열을 한번에 뒤집을 수 있다.

이 방법을 사용하려면, re 라는 정규 표현식을 사용하여 사용할 문자(영문과 숫자)만 따로 필터링하여 문자열을 재구성해야한다.(정규 표현식은 따로 포스팅할 예정)

from typing import re

def isPalindromeThird(s: str) -> bool:
    s = s.lower()
    #정규식으로 불필요한 문자 필터링
    # s 안에 a-z, 0-9가 아닌 모든 문자를 공백으로 바꾸는 정규 표현식
    s = re.sub('[^a-z0-9]', '', s)

    # [::-1] -> 문자열을 뒤집는 슬라이싱 기
    return s == s[::-1]
    
    
if __name__ == '__main__':
    s = "A man, a plan, a canal: Panama"
    s2 = "race a car"
    print(isPalindromeThird(s))
    print(isPalindromeThird(s2))

---