[파이썬 알고리즘] 6장 - 문자열 조작 (valid palindrome)

leetcode.com/problems/valid-palindrome/

Valid Palindrome - LeetCode

 

<문제>

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

Note: For the purpose of this problem, we define empty string as valid palindrome.

 

 

<예시>

Input: "A man, a plan, a canal: Panama"

Output: true

 

---

# 유효한 팰린드롬
# https://leetcode.com/problems/valid-palindrome/

def answer_2(s:str):
    new_s = []
    for x in s.lower():
        if x.isalnum():
            new_s.append(x)
            
    while len(new_s) > 1:
        if new_s.pop(0) != new_s.pop():
            return False
    return True

# 리스트에서 뒤에서 pop하는 것은 O(1)
# 리스트에서 앞에서 pop(0)하는 것은 O(n) -> 비효율적


def answer_3(s:str):
    deque: Deque = collections.deque()
    for x in s.lower():
        if x.isalnum():
            deque.append(x)
            
    while len(deque) > 1:
        if deque.popleft() != deque.pop():
            return False
    return True

# deque에서 뒤에서 pop하는 것은 O(1)
# deque에서 앞에서 popleft하는 것은 O(1) -> 성능 개선

 

<알게된 것>

 

* isalpnum

문자가 숫자 혹은 영어로 구성되어 있는 지 판단해주는 함수

 

* deque

double ended queue의 줄임말으로, 양뱡향에서 데이터를 삽입/삭제할 수 있는 자료구조

끝에서 삽입/삭제 - O(1)

앞에서 삽입/삭제 - O(1)

 

파이썬 리스트의 경우 (포인터의 배열 + 각 객체는 불연속적인 공간에 존재)

끝에서 삽입/삭제 - O(1)

앞에서 삽입/삭제 - O(n)

 

따라서 앞 혹은 뒤 양방향에서 데이터를 제거해야 하는 경우 list보다 queue를 사용하면 성능을 향상시킬 수 있다.

(참고) excelsior-cjh.tistory.com/96

 

* 리스트[:]

list[:] 해서 변수에 할당하면 동일한 메모리 참조가 아니라, 복사본을 가리키게 된다.

pythonic한 복사 방법인 것이다.