[String Manipulation] Intro & Valid Palindrome

박상길님의 <파이썬 알고리즘 인터뷰>를 보며 문제를 풀고 정리한 것입니다. 

1. 문자열 조작 (String Manipulation)이란 

문자열을 변경하거나 분리하는 등의 여러 과정을 말함

 

2. 문자열 처리와 관련한 알고리즘이 쓰이는 대표적인 분야

• 정보 처리 분야: 어떤 키워드로 웹 페이지를 탐색할 때 문자열 처리 애플리케이션을 이용한다. 또한 많은 정보가 문자열로 구성되어 있으므로 문자열 처리는 정보 처리에 핵심이 된다. 
• 통신 시스템 분야: 문자열 데이터 전송은 문자열 처리 알고리즘이 나오게 된 기원이기도 하며, 데이터 전송에서 문자열 처리는 매우 중요하다. 
• 프로그래밍 시스템 분야: 프로그램은 그 자체가 문자열로 구성되어 있고, 컴파일러나 인터프리터에서 문자열을 해석하고 기계어로 번환하는 과정에서 정교한 문자열 처리 알고리즘이 사용된다. 

 

3. 학습 목표

• 문자열과 관련된 문제를 풀면서 문제 해결능력을 기른다. 
• 파이썬의 문자열 자료형에는 어떤 기능들이 제공되는지 알아본다. 
• 문자열 조작과 처리에 어떤 기법들이 쓰이는지 알아본다. 

 

4. 유효한 팰린드롬 (Valid Palindrome)

문제 출처: https://leetcode.com/problems/valid-palindrome/

문제

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Example 1:
Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:
Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome.

 

Constraints:

• 1 <= s.length <= 2 * 105
• s consists only of printable ASCII characters.

문제 이해 (사고의 흐름)

1. 문자열이 주어지고 대소문자를 구분하지 않고 알파벳과 숫자만 가지고 이 문자열이 팰린드롬인지 아닌지 true/false로 리턴하는 문제구나

2. 문자열은 항상 주어지나? 음. 1 <= s.length <= 2 * 105이라고 했으니 1자 이상은 무조건 주어지는구나.

3. 그럼 1글자 일 때는 팰린드롬인가? 팰린드롬의 정의가 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters)이니까 1글자도 팰린드롬 true이겠구나.

4. 그럼 필요한 것은 

    1) s에서 알파벳과 숫자만 추출해야하고, 

    2) 대/소문자 구분할 필요없게 모두 다 소문자로 바꾸자. 

    3) 그 다음 앞에서 하나씩, 뒤에서부터 하나씩 문자를 비교하면서 나아가자

    4) 어짜피 글자의 반 정도까지만 검사하면 되고, 그 전에 다른게 있다면 false로 early return 해버리자. 

    5) 1, 2번 과정은 list comprehension을 사용하면 간단하게 할 수 있을 듯

 

실수

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.에서 

only alphanumeric을 only the alphabet이라는 줄 알고 숫자도 다 무시해버렸다. 

문제를 정확히 읽고 이해하는 것이 먼저다! 

 

첫 번째 풀이

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = [character.lower() for character in s if 
            	('a' <= character and character <= 'z') or 
                ('A' <= character and character <= 'Z') or 
                ('0' <= character and character <= '9')]

        for inx in range(len(strs)//2):
            if strs[inx] != strs[-1-inx]:
                return False

        return True

 

리스트로 변환하는 것을 이용한 풀이

• isalnum(): 영문자, 숫자 여부를 판별하는 함수를 사용해서 위에서 처럼 지루한 if문을 사용하지 않아도 된다. 
• pop(): 파이썬의 리스트는 pop() 함수를 사용해서 인덱스를 지정할 수 있는 점을 활용하고, 하나씩 빼가면서 확인한다.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = [character.lower() for character in s if (character.isalnum())]

        for inx in range(len(strs)//2):
            if strs.pop(0) != strs.pop():
                return False

        return True

 

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

위의 코드에서  속도를 조금 더 높이는 최적화는 어떻게 할 수 있을까? Deque를 명시적으로 선언한다. 

• Deque: queue는 FIFO 방식으로 작동하는 반면 Deque는 양방향 큐로 앞, 뒤 양쪽에서 요소를 추가하거나 제거할 수 있다.
  이를 사용하는 것이 속도 최적화에 도움이 되는 이유는 위에서 사용한 리스트 연산은 O(n)이지만 Deque는 O(1)로 접근이 가능하다. 

import collections


class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs: Deque = collections.deque()

        for char in s:
            if char.isalnum():
                strs.append(char.lower())

        for _ in range(len(strs)//2):
            if strs.popleft() != strs.pop():
                return False

        return True

 

슬라이싱 사용

• 슬라이싱: 내부적으로 C로 구현되어 있어서 빠르게 동작한다. 파이썬에서 문자열 슬라이싱은 위치를 지정하면 해당 위치의 배열 포인터를 얻게 되며  이를 통해 연결된 객체를 찾아 실제 값을 찾아낸다. Lst[ Initial : End : IndexJump ]
• 정규식: 정규식 패턴은 일련의 바이트 코드로 컴파일된 다음 C로 작성된 일치 엔진에 의해 실행된다. 

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        s = re.sub('[^a-z@0-9]', '', s)
        
        return s == s[::-1]

 

정리

• 문자열을 별도로 리스트로 매핑하는 등의 처리에 상당한 연산 비용이 든다. 
• 대부분의 문자열 작업을 슬라이싱으로 처리하는 편이 가장 빠르다. 
• C와 같은 컴파일 언어는 파이썬 같은 인터프리터 언어에 비해 더욱 좋은 성능을 낸다. 

 

 

Reference

https://leonkong.cc/posts/python-deque.html

https://docs.python.org/ko/3/howto/regex.html

https://www.geeksforgeeks.org/python-list-slicing/

https://docs.python.org/ko/3/library/re.html#re.sub