[Python/파이썬] 문자열 처리 - Palindrom(팰린드롬)

 

※ 이 글의 작성자는 SW 비전공자입니다. 

※ 개인적으로 공부하고 있는 내용을 정리하고 있는 글로 잘못 된 부분이 있다면 댓글을 남겨주세요.

---

 

1. 팰린드롬

 

  'Palindrome'(팰린드롬) 이란 어떤 단어나 특정 문장을 뒤집어도 같은 말이 되는 것을 말한다. 우리나라에서는 '회문'이라는 단어로도 사용된다고 한다. 예를들면 '일요일', '스위스'같은 단어가 있다. 알고리즘 인터뷰 책에서는 첫 문제로 이 팰린드롬을 다루고있어 공부한 내용을 정리해보았다.

 

 

2. 'Valid Palindrome' 문제

 

  '알고리즘 인터뷰'에서는 '리트코드'라는 사이트의 문제들을 가지고 풀이 및 해설한다. 아래는 리트코드의 'Valid Palindrome'의 문제이다.

(리트코드 - Valid Palindrome : https://leetcode.com/problems/valid-palindrome/)

 

https://leetcode.com/problems/valid-palindrome/

 

-. 주어진 문자열이 팰린드롬인지 확인하기 : 영문자와 숫자만을 대상으로 한다.

   (특수문자는 제외되어야 함)

-. 입력은 string, 출력은 Boolean type이다.

 

Case1 입력 : "A man, a plan, a canel : Panama" 출력 : true Case2 입력 : "race a car" 출력 : false

 

 

3. 풀이

 

  다음과 같은 순서로 해결하고자 했다.

 

-. 주어진 문자열의 특수문자 및 공백 제거

-. 주어진 문자열을 역순으로 배열하는 방법

   : 문자열을 for문을 통해 역순 배열하기, 문자열 슬라이싱하기

-. 주어진 문자열과 역순 배열한 문자열 비교하여 True, False 리턴하기

 

 

1) 특수문자 및 공백 제거

 

<코드>

import re

str_test = "A man, a plan, a canal: Panama" 
 
#대소문자 구분 없애기 위해 lower 적용
str_test = str_test.lower()
 
#띄어쓰기 제거
str_test = str_test.replace(" ", "")

#특수문자 제거
str_test = re.sub('[^A-Za-z0-9가-힣]', '', str_test)
print(str_test)

 

amanaplanacanalpanama

 

-. .lower() 함수는 문자열 처리 함수로 영문자를 모두 소문자화한다.(반대로 대문자는 .upper()를 사용)

-. .replace() 함수는 문자열의 특정문자를 대체하는 함수이다. 위에 사용하는 코드는 공백(스페이스)를 제거한다.

-. re.sub() 함수는 내장모듈인 re의 함수로 정규표현식을 사용해 특정 문자 형식(숫자,알파벳 등)을 쉽게 치환할 수 있다. 위에 적용한 코드는 알파벳,한글을 제외한 나머지를 공백으로 바꾸는 부분이다.

(re 모듈은 자주 쓰이는 내장 모듈로 따로 포스팅 할 예정)

 

 

 

2-1) 역순배열 - for문 통해 역순 배열하기

 

  -. 역순으로 배열하기 위해 아래 코드를 적용(다른 티스토리 블로그를 참고함 - 하단에 링크 첨부)

  -. 빈 문자열을 선언하여 각 문자를 for문을 통해 문자열 끝으로 붙인다.

  -. 밑에 for문 출력과정을 보면 이전 루프에서 생성했던 문자열을 계속 뒤로 붙이는 알고리즘이다.

 

<코드>

import re

str_test = "A man, a plan, a canal: Panama" 
 
#대소문자 구분 없애기 위해 lower 적용
str_test = str_test.lower()
 
#띄어쓰기 제거
str_test = str_test.replace(" ", "")

#특수문자 제거
str_test = re.sub('[^A-Za-z0-9가-힣]', '', str_test)
print(str_test)

#역순을 위한 빈문자열 선언
str_reverse= ''

# 문자열 역순으로 배열하기
for char in str_test:
    str_reverse = char + str_reverse
    print(str_reverse)

 

a
ma
ama
nama
.
.
<중략>
.
.

naplanacanalpanama
anaplanacanalpanama
manaplanacanalpanama
amanaplanacanalpanama

 

 

2-2) 문자열을 역순 슬라이싱하기

 

  위에 for문을 활용한 방식은 루프를 돌기 때문에 처리 속도가 느린 단점이 있다. 나중에 결과를 비교해보면 알겠지만 for문을 활용한 방법의 처리속도가 100ms라면 역순 슬라이싱 방법은 40ms이다. 책에 따르면 슬라이싱 방법은 내부적으로 C로 구현되어 있어 속도가 빠르다고 한다.

 

  아래 코드는 위 2-1) 코드에서 역순 되는 부분만 대체한 것이다.

 

<코드>

#문자열 역순으로 슬라이싱하기
str_reverse = str_test[::-1]
          
print(str_reverse)

 

amanaplanacanalpanama

 

---

※ 문자열 슬라이싱

 

  리스트 슬라이싱하는 방법이 있지만 파이썬에서는 문자열 슬라이싱 기능도 있다. 아래 예시로 간단히 정리

 

-. 파이썬의 첫 요소의 인덱스는 무조건 0이다.

-. 슬라이싱에서 a[0:3]의 3은 3번째요소까지가 아니라 그전 요소까지다. 따라서 0,1,2번째 요소를 출력

-. 역순으로 출력하려면 a[::-1]과 같이 step 값을 -로 입력하면 된다.

 

<코드>

a = 'abcdefghijk'

#0번째 ~ 2번째 요소까지 출력
print(a[0:3])

#1번째~2번째 요소를 2 step으로 출력
print(a[1:5:2])

#역순 출력(-1 step으로 출력)
print(a[::-1])

 

abc
bd
kjihgfedcba

---

 

 

2-3) 리스트를 사용해서 reverse 함수 사용하기

 

  리스트를 사용하여 역순 배열하는 방법도 있다. 아래 사진과 같이 문자열을 리스트화 시키고 reverse()함수를 사용하면 된다. 문자열을 list로 감싸면 각 문자별로 구분하여 리스트화 된다.(아래 결과 참고)

 

<코드>

str_list = list(str_test)
print("원본:", str_list)

str_list.reverse()
print("역순:", str_list)

 

원본: ['a', 'm', 'a', 'n', 'a', 'p', 'l', 'a', 'n', 'a', 'c', 'a', 'n', 'a', 'l', 'p', 'a', 'n', 'a', 'm', 'a']
역순: ['a', 'm', 'a', 'n', 'a', 'p', 'l', 'a', 'n', 'a', 'c', 'a', 'n', 'a', 'l', 'p', 'a', 'n', 'a', 'm', 'a']

 

 

4. 답안제출 및 결과

 

1) for문 통해 역순 배열하기

 

<제출 코드>

import re
class Solution:
    def isPalindrome(self, s: str) -> bool:
        #대소문자 구분 없애기 위해 lower 적용
        str_test = s.lower()
        #띄어쓰기 제거
        str_test = str_test.replace(" ", "")
        #영문자, 숫자빼고 제거
        str_test = re.sub('[^A-Za-z0-9가-힣]', '', str_test)
		
        #역순 배열하기
        str_reverse= ''
        for char in str_test:
          str_reverse = char + str_reverse
		
        # 원본, 역순 비교 결과 리턴
        if str_test == str_reverse:
          return True
        else:
          return False
        
        
sol = Solution()

s = "A man, a plan, a canal: Panama"
sol.isPalindrome(s)
s = "race a car"
sol.isPalindrome(s)

 

 

2) 문자열 슬라이싱 사용

 

<제출 코드>

import re
class Solution:
    def isPalindrome(self, s: str) -> bool:
        #대소문자 구분 없애기 위해 lower 적용
        str_test = s.lower()
        #띄어쓰기 제거
        str_test = str_test.replace(" ", "")
        #영문자, 숫자빼고 제거
        str_test = re.sub('[^A-Za-z0-9가-힣]', '', str_test)

        str_reverse = str_test[::-1]
          
        if str_test == str_reverse:
          return True
        else:
          return False
        
        
sol = Solution()

s = "A man, a plan, a canal: Panama"
sol.isPalindrome(s)
s = "race a car"
sol.isPalindrome(s)

 

 

위에서 언급했지만 리트코드에서 2가지 코드를 돌려 속도를 비교해보면 슬라이싱 방법이 월등히 빠르다

(40ms가 슬라이싱 방식)

<속도 비교>

 

 

4. 진행중 에러사항(막힌 부분)

 

  처음에 클래스 함수 호출을 클래스명을 통해 직접 호출하는 방식으로 적용하니 아래와 같은 에러가 발생했다.

 

<코드>

class Solution:
    def isPalindrome(self, s: str) -> bool:
        return True

s="abc"

#Solution 클래스 이름 통해 메소드 직접 호출
print(Solution.isPalindrome(s))

 

TypeError: isPalindrome() missing 1 required positional argument: 's'

 

TypeError: isPalindrome() missing 1 required positional argument: 's'

 

-> isPalindrome이라는 함수가 클래스의 함수. 클래스의 함수를 직접 사용하려고 했기에 실행이 안됨

-> 클래스 객체를 따로 선언 후 객체를 통해 함수 접근해야 됨

    (만약 객체를 선언하고 싶지 않다면 self 를 사용하면 안된다.)

 

예전에 비슷한 내용을 포스팅해서 다시 복습겸 링크 첨부 함.

(관련 포스팅 : 2021.03.27 - [코딩/Python] - [Python/파이썬] Class(클래스) 메서드 self 설명

 

 

 

  '알고리즘 인터뷰' 책에서는 리스트 변환 방식, 슬라이싱 방식 말고도 '데크 자료형을 이용한 최적화'방식을 다루고 있는데 이 부분은 따로 내용을 남기지 않고 개인적으로 공부해볼 예정이다.

---

참고링크1 : 파이썬 문자열 공백제거하기 https://appia.tistory.com/234

참고링크2 : 파이썬 문자열에서 한글,영문만 남기기 https://signing.tistory.com/74

참고링크3 : 파이썬 TypeError 오류 해결 https://kkamikoon.tistory.com/119