Valid Palindrome (Deque)

드디어 파이썬 알고리즘 인터뷰 책을 좀 읽어보게 됐다. LeetCode에서 튜토리얼을 진행할 때는 자바로 했지만 프로그래머스나 혼자 풀 때는 파이썬 언어를 사용하고자 한다. 책에서 소개하는 문제들을 먼저 풀어보고 다른 사람들의 풀이나 책에 나온 내용들을 기반으로 개선방안을 학습하며 포스팅할 예정이다.

 

이번 문제는 LeetCode의 Easy 문제인 Valid Palindrome이다.

Valid Palindrome - LeetCode

문제의 조건은 다음과 같다.

• 문자열이 주어진다.

• 문자열에서 알파벳, 숫자 문자만 따진다고 할 때 이 문자열이 회문인지 검사하라.

회문은 뒤집어도 똑같은 문자열을 의미한다. 한국어로는 "소주 만 병만 주소" 라던가, 영어로는 앨리스의 "Was it a cat I saw?" 같은 문자열을 들 수 있는데 이들은 거꾸로 읽어도(물론 특수문자는 제외하고) 같은 문자열이기 때문에 회문이라 하는 것이다.

 

파이썬에서 이 회문을 확인하려면 가장 먼저 떠오르는 것은 list 클래스의 reverse() 메서드다. 파이썬의 inline list comprehension(한국어로 어떻게 써야 할지 모르겠지만)을 활용해서 문자열을 리스트로 만들고 이를 뒤집은 것과 그렇지 않은 것을 비교하면 풀 수 있지 않을까? 이를 바탕으로 작성한 코드는 다음과 같다.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        only_characters = [x.lower() for x in s if x.isalnum()]
        given_string = "".join(only_characters)
        only_characters.reverse()
        given_string_reverse = "".join(only_characters)
            
        return given_string == given_string_reverse

계속 까먹는 점이지만 리스트의 reverse 메서드는 In Place 정렬이기 때문에 역순의 리스트를 반환하는 게 아니라 메서드가 호출된 리스트 객체의 내부를 변경한다. 그래서 위처럼 먼저 문자열로 만들고 뒤집어서 다시 문자열로 만들어서 마지막에 비교하는 방식으로 구현하였다.

실행결과 상위 80%의 나쁘지 않은 성능이었는데 다른 사람들은 어떻게 풀었을까? 절반 정도 되는 24ms의 풀이를 살펴보니 다음과 같았다.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s1 = ''.join(filter(str.isalnum, s))
        
        if s1.lower() == s1[::-1].lower():
            return True
        return False

놀랍게도 약 4줄의 코드로 완성한 것을 볼 수 있었는데 여기서는 문자열 슬라이싱을 사용하여 문자열을 뒤집고 있었다. 위의 filter 메서드는 문자열 내의 문자에 대하여 해당하는 조건(isalnum, 즉 문자가 알파벳 또는 숫자인지)에 해당하는 문자만 배열로 반환하는 역할인데 이를 합쳐서 문자열로 만든 후 [::-1]처럼 슬라이싱으로 뒤집고 있는 것이다.

 

확실히 배열을 뒤집어서 다시 문자열로 join 하는 것보다는 이미 join 된 문자열을 뒤집을 수 있는 방법을 사용하는 것이 더 빠를 것이다. 책에서도 문자열 슬라이싱은 굉장히 빠르다고 하니 이를 활용할 수 있는 상황이 보면 잊지 말고 활용해야 할 것이다.

 

재밌는 것은 만약 아래와 같은 코드로 풀어보면 200ms라는, 하위 2~3% 정도의 매우 낮은 성능을 볼 수 있었다. 문자열의 양 끝 문자를 하나씩 pop 메서드로 제거하고 비교해보면서 풀어보는 방법인데 이 pop 연산이 문제가 되는 것이다.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        only_characters = [x.lower() for x in s if x.isalnum()]
        while len(only_characters) > 1:
            if only_characters.pop(0) != only_characters.pop():
                return False
            
        return True

이는 책에서도 권장하지 않는 방법으로 보여준 예시인데 리스트의 pop 메서드는 O(n)의 시간 복잡도를 갖고 있기 때문에 매우 느리다. 지금 이 문제에서는 리스트의 중간을 참조할 필요가 없고 양 끝단의 값만 빼면 되기 때문에 collections 모듈의 deque 클래스를 활용해볼 수 있다.

collections — Container datatypes — Python 3.9.1 documentation

deque 클래스는 맨 왼쪽(popleft)이나 오른쪽(pop)의 값을 제거하는 연산의 경우 O(1)의 시간 복잡도를 가지기 때문에 더 효율적이다. 그리고 배열을 생성자로 받아서 초기화할 수 있기 때문에 이전처럼 list comprehension과 같이 사용할 수 있다.

from collections import deque


class Solution:
    def isPalindrome(self, s: str) -> bool:
        only_characters = deque([x.lower() for x in s if x.isalnum()])
        
        while len(only_characters) > 1:
            if only_characters.popleft() != only_characters.pop():
                return False
            
        return True

실행 결과는 44ms로 list comprehension과 reverse 메서드를 사용한 것과 비슷하다. 하지만 list에서 pop(), pop(0) 메서드를 활용한 것에 비하면 약 5분의 1로 많이 줄어든 것을 볼 수 있다.

 

그럼 리스트와 덱(deque)의 pop 메서드는 얼마나 속도 차이가 나는 걸까? 65535 크기의 문자 배열을 선언하고 맨 왼쪽, 오른쪽 값을 제거하는 메서드를 반복 연산하는 방법으로 테스트해본 결과 다음처럼 약 30배가 넘게 차이 나는 것을 볼 수 있다.

>>> type(a)
<class 'list'>
>>> type(b)
<class 'collections.deque'>
>>> type(list_as_queue)
<class 'function'>
>>> type(deque_as_queue)
<class 'function'>
>>> def time_checker():
...     start_time = time.time()
...     list_as_queue(a)
...     end_time = time.time()
...     print("Using list as queue", end_time - start_time)
...     start_time = time.time()
...     deque_as_queue(b)
...     end_time = time.time()
...     print("Using deque as queue", end_time - start_time)
...
>>> time_checker()
Using list as queue 0.17962265014648438
Using deque as queue 0.005059242248535156

그렇기 때문에 절대로 리스트를 큐로 사용하는 일은 없어야 할 것이다.