[leetcode] 125. valid palindrome

강아지 이름은 봄이·2023년 6월 23일

0. 문제 링크

1. 나의 풀이

✍️ 설명

입력으로 들어온 문자열을 모두 소문자로 바꾼다.
왼쪽을 가리키는 인덱스 변수(left), 오른쪽을 가리키는 인덱스 변수(right)를 각각 0과 len(s)-1 로 설정한다.
왼쪽 변수의 값이 오른쪽 변수의 값보다 커질 때까지 좌측 값과 우측 값을 비교하는 과정을 거치는데
각 포인터가 가리키는 값이 문자 혹은 숫자가 아니라면 왼쪽 포인터는 오른쪽으로(+1), 오른쪽 포인터는 왼쪽으로(-1) 이동한다.

🖥️ 실행 코드

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0 #왼쪽을 가리키는 포인터 변수
        right = len(s)-1 #오른쪽을 가리키는 포인터 변수
        s = s.lower()
        res = True
        while left <= right:
            #왼쪽 포인터가 가리키는 변수 값이 숫자, 영문자가 아닐때까지 오른쪽으로 이동
            while not (s[left].isalpha() or s[left].isdigit()):
                left += 1
                if left >= len(s): #범위에 넘어가면 반복 종료
                    return res
            #오른쪽 포인터가 가리키는 변수 값이 숫자, 영문자가 아닐때까지 왼쪽으로 이동
            while not (s[right].isalpha() or s[right].isdigit()):
                right -= 1
                if right < 0: #범위에 넘어가면 반복 종료
                    return res

            if s[left] != s[right]: #두 글자가 다르면 팰린드롬이 아님
                res = False
                return res
            else: #같으면 한 칸 이동
                left += 1
                right -= 1
        return res

🔥 성능 확인

2. 다른 코드

책 <파이썬 알고리즘 인터뷰>를 참고함

2-1. 리스트 활용 방법

✍️ 설명

입력받은 문자열을 isalnum() 함수를 이용하여 영문자 & 숫자 체크 후, 영문자 혹은 숫자라면 리스트에 넣는다.
리스트의 길이가 0 또는 1이 되기 전까지 리스트 맨 앞 원소와 맨 뒤 원소를 하나씩 제거하면서, 둘이 다르면 팰린드롬이 아니므로 False를 반환하고 종료한다.
2번이 끝까지 실행됐으면 팰린드롬이므로 true를 반환하고 종료한다.

🖥️ 실행 코드

class Solution:
    def isPalindrome(self, s: str) -> bool:
        alnum_list = [] #숫자와 영문자만 담을 리스트
        for char in s:
            if char.isalnum():
                alnum_list.append(char.lower()) #소문자로 바꿔서 리스트에 추가
        
        while len(alnum_list) > 1:
            if alnum_list.pop() != alnum_list.pop(0):
                return False
        return True

🔥 성능 확인

리스트의 pop()처럼 인덱스번호를 지정 안하면 맨 뒤의 원소를 제거하는데, 이 때는 시간복잡도가 O(1) 이다. 반면에 pop(0)은 길이가 n인 리스트의 맨 앞까지 탐색한 다음에 pop하기 때문에 시간복잡도가 O(n) 이다. 그래서 성능을 확인해보면 좋지 않음을 볼 수 있다.

2-2. deque 활용하기

deque는 파이썬에서 큐를 구현하기 좋은 라이브러리인데, 리스트의 pop(0)과 같은 기능인 popleft()가 있다. 시간복잡도는 O(1)로 훨씬 효율적이다. 리스트를 deque로 바꿔 코드를 다시 작성해보자.

🖥️ 실행 코드

from collections import deque #deque사용을 위해 임포트
class Solution:
    def isPalindrome(self, s: str) -> bool:
        queue = deque([]) #deque 생성
        for char in s:
            if char.isalnum():
                queue.append(char.lower())

        while len(queue) > 1:
            if queue.popleft() != queue.pop():
                return False
        return True