[문자열 조작] 01 유효한 팰린드롬(Valid Palindrome)

<LeetCode 문제>

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

Valid Palindrome - LeetCode

주어지는 문자열이 팰린드롬(뒤집어도 같은 문자열)인지 확인하는 문제입니다.

이때, 제약조건으로 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 합니다.

<풀이>

먼저 대소문자 구분을 없애고, 영문자와 숫자만을 보기 위한 전처리가 필요합니다.

그 이후, 전처리된 문자열을 뒤집어서 같은지 확인합니다.

 

처음 문제를 풀었을 때의 코드는 다음과 같습니다

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower().replace(' ','') #모두 소문자로+공백제거
        refined_s = '' #숫자,문자만 남길 문자열
        for one_s in s:
          if one_s.isdigit() or one_s.isalpha(): #숫자거나 문자일때만
            refined_s+= one_s
        
        if refined_s == refined_s[::-1]: #뒤집어도 같다면
            return True
        else:
            return False

 

위 코드에서

1. isdigit과 isalpha를 묶어서 isalnum으로 한 번에 처리할 수 있으며

2. 뒤집은 문자열과 원래 문자열이 같은지 확인해서 if문으로 처리하는 것이 아니라 ==의 반환 값 자체를 반환하면 됩니다.

 

따라서 리팩토링한 코드는 다음과 같습니다.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower().replace(' ','') #모두 소문자로+공백제거
        refined_s = '' #숫자,문자만 남길 문자열
        for one_s in s:
          if one_s.isalnum(): #숫자거나 문자일때만
            refined_s+= one_s
        
        return refined_s == refined_s[::-1] #뒤집어도 같은지

 

정규식을 이용해서 숫자, 문자만 남기는 전처리과정을 간단히 할 수도 있습니다.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower() #모두 소문자로
        s = re.sub('[^a-z0-9]','',s) #문자,숫자만 남기기
        return s == s[::-1]

 

뒤집은 문자열이 원래 문자열과 같은지 확인할 때 슬라이싱을 이용했는데, deque을 통해 앞, 뒤를 일일이 확인하는 과정을 거쳐도 됩니다.

class Solution:
    def isPalindrome(self, 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

 

하지만 슬라이싱이 내부적으로 매우 빠르게 동작하기 때문에, 문자열 조작에서 항상 슬라이싱을 우선으로 사용하는 편이 좋습니다.

<학습내용>

1. isalnum()은 영문자, 숫자 여부를 판별(isalpha(), isdigit()는 영문자만, 숫자만 판별)
2. 파이썬의 리스트는 pop() 함수에서 인덱스를 지정할 수 있고, 0을 지정하면 맨 앞의 값을 가져옴
3. list의 pop(0)은 O(n)이고, deque의 popleft()는 O(1)
4. [::-1]로 뒤집기. [:]를 통해 참조가 아닌 값을 복사
5. 슬라이싱은 매우 빠르게 동작

<학습이 필요한 내용>

1. 정규표현식(https://wikidocs.net/1669)
2. 파이썬 메소드마다의 시간복잡도(https://wayhome25.github.io/python/2017/06/14/time-complexity/)

 

https://github.com/HoYoungChun/Algorithm_PS/blob/master/String/LC_125.py

GitHub - HoYoungChun/Algorithm_PS: Baekjoon Online Judge, Programmers problem solving by Python, C++