유효한 펠린드롬 문제

 

코딩 책을 샀다. "파이썬 알고리즘 인터뷰" 이 책을 시작으로 반드시 기필코 코딩테스트라는 것을 꼭 붙고 말겠다.

 

책의 6장까지는 기초적인 그리고 개념적인 부분들이 많다. 본격적인 알고리즘에 대한 내용은 7장부터 시작이다. 먼저 6장에서는 문자열 처리에 대한 문제로 첫 스타트를 끊는다.

리트코드의 문제들로 이뤄진 만큼 피드백 받기 좋고, 효율성에 대한 부분을 체크하기 좋아서 추천할만하다. 저자 역시 무료로도 충분히 학습이 가능하다고 하니 책을 끝내고 나서 자유롭게 또 풀어보는 시간이 왔으면 좋겠다.

 

문제: " 주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다."

 

아래의 예시 처럼 input 이 주어지면 영문자, 숫자를 제외하고 우선적으로 전처리가 필요하다. 

필요한 전처리는 영어를 모두 소문자 또는 대문자로 통일시켜라. 그리고 알파벳과 숫자를 제외한 것은 모조리 다 지워서 띄워쓰기 없이 다 붙여라.

그래서 떠오르는대로 막짜본 코드가 아래와 같다. 정규표현식을 사용할 수 있게 해주는 re 모듈로 부터 sub 함수를 사용하였다. 그래서 sub 함수에서 [^a-zA-Z0-9] 가 의미하는 것이 곧 영어랑 숫자를 제외한다는 것이고, 그런 것들을 전부 없애주도록 하였다. 

 

그런 다음 for 문을 돌아서 전부 소문자로 바꿔주었고, string 을 거꾸로 했을 때와 비교하여서 거꾸로 했을 때랑 동일한지를 확인했다. 

그리고 string.lower() 하면 string 전체가 lower case로 바뀌는데, for 문을 돌린건 ... 좀 .. 고치자.

    import re
    def isPalindrome(self, s: str) -> bool:
        s = re.sub('[^a-zA-Z0-9]', '', s)
        s2 = ''
        for i in s:
            s2 += i.lower()
        
        if s2 == s2[::-1]:
            return True
        else:
            return False

 

책에 나와 있는 코드를 보면 아래와 같다. 먼저 정규표현식 대신에 string.isalnum() 함수를 사용했다. isalnum() 이라는 것은 알파벳 또는 숫자면 True를 아니면 False를 리턴해주는 내장함수이다. 내장함수 하나 외우고 간다. 

아래의 코드는 문제 해결은 가능하지만 굉장히 비효율적이다. while 문을 돌면서 계속 if 문을 수행해야하는 것 같다.

 

    import re
    def isPalindrome(self, s: str) -> bool:
        basket = []
        
        for i in s:
            if i.isalnum():
                basket.append(i.lower())
        
        while len(basket) > 1:
            if basket.pop() != basket.pop(0):
                return False
        
        return True

 

리스트의 pop(0) 은 복잡도가 n 에 해당한다. 배열을 다시 n 개만큼 죽죽 재배열해야 해서 그렇다. 그래서 collections 모듈의 deque 함수를 사용하였다. 아래는 게재된 코드이다. 데크라는 자료구조를 사용하게 되면, list 에서 큐의 개념으로 앞에 것을 빼오는데 시간복잡도가 1 이 든다. 즉 list 의 마지막 append 된 원소를 빼주는 pop() 과 동일한 시간이 소요된다. pop(0) 대신에 popleft() 를 사용하였다.

    from collections import deque
    def isPalindrome(self, s: str) -> bool:
        
        basket = deque()
        
        for i in s:
            if i.isalnum():
                basket.append(i.lower())
        
        while len(basket) > 1:
            if basket.pop() != basket.popleft():
                return False
        
        return True

 

아직까지는 쉬워! 좋아.!

 

 

 

 

 

 

 

 

ref) 파이썬 알고리즘 인터뷰