[Python/LeetCode] 125. Valid Palindrome

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

주어진 문자열이 팰린드롬인지 아닌 지 판별하시오.

 

---

배경

팰린드롬(Palindrome)

- 앞뒤가 똑같은 단어나 문장 

- ex. A man, a plan, a canal: Panama (문장부호는 무시했을 때 기준)

 

입력 : 문자열 s

출력 : s가 팰린드롬이면 true, 아니면 false

---

전략 

일단 우리는 s에서 문장부호 같은 것들을 다 제거하고 볼거임. 그리고 대문자도 소문자도 변환해서 볼거임. 그러고 난 후에, 뒤집은 게 원본과 같다면? 팰린드롬.

 

정리하면,

1. low_str = s.lower() 해서 새로운 문자열에 저장하고

2. 소문자가 아닌 것들을 다 제거할거임. char.isalnum()으로 문자 하나하나씩 비교하자.

3. 그 후, if my_str == my_str[::-1]: 같은 식으로 뒤집은 문자열과 비교를 함.

4. 같으면 true, 다르면 false 출력.

---

공부내용

* str.lower() 메서드

문자열의 lower 메서드는 새로운 문자열을 반환하고(당연, 문자열은 불변 객체니까), 비알파벳 문자들은 그대로 유지됨.

 

* 문자열 뒤집기
문자열을 뒤집는 건 여러 방법이 있음. 일단 슬라이싱이 젤 쉬움. 그리고 아래 글에선 슬라이싱이 덜 빠르게 나왔는데, 책에 따르면 실제론 슬라이싱이 대부분 경우에서 젤 빠른듯.
https://osg.kr/archives/1973

 

* 알파벳 문자(Alphanumeric characters)

Alphanumeric characters are made up of the 26 letters of the alphabet (A through Z) and the digits 0 through 9. So, 1, 2, q, f, m, p, and 10 are all examples of letters and numbers.

https://unacademy.com/content/cat/study-material/data-interpretation-and-logical-reasoning/alphanumeric-characters/

 

* 문자열에서 비알파멧 문자 제거

일단 내가 당장 쓸만한 방법은 isalnum()인듯.

https://letzgorats.tistory.com/entry/Remove-Non-alphanumeric-Characters-in-Python

 

* str.isalpha() vs str.isalnum()

전자는 영어한글, 후자는 영어한글숫자 시 True.

https://it-neicebee.tistory.com/43

 

---

1차 풀이

class Solution:
    def isPalindrome(self, s: str) -> bool:
        low_str = s.lower()
        fin_str = []
        for char in low_str:
            if char.isalnum():
                fin_str.append(char)

        if fin_str == fin_str[::-1]:
            return True
        else:
            return False

전략에 쓴 대로 가장 직관적으로 풀어 봤다. 리스트로 변환해서 append.

POP 사용 풀이

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = []
        for char in s:
            if char.isalnum():
                strs.append(char.lower())

        # 팰린드롬 여부 판별
        while len(strs) > 1:
            if strs.pop(0) != strs.pop():
                return False

        return True

뒤에 원본 문자열과 뒤집은 문자열이 같은 지 비교해 팰린드롬인지 판별하는 파트는, 위처럼도 구현 가능하다. (그러나 비효율적)

pop()은 O(1), pop(0)은 O(n)으로, n번 반복하니 O(n^2)

* 참고) 위 시간복잡도 이유

1. pop()의 동작

• 기본적으로 pop()은 리스트의 마지막 요소를 제거하고 반환합니다.
• 리스트는 메모리에서 연속적인 배열로 관리되므로, 마지막 요소를 제거하는 작업은 단순히 끝 위치를 가리키는 포인터를 이동시키는 작업만 필요합니다.
• 따라서, 이 작업은 **O(1)**의 시간 복잡도를 가집니다.

---

2. pop(0)의 동작

• pop(0)은 리스트의 첫 번째 요소를 제거합니다.
• 리스트는 동적 배열로 구현되어 있기 때문에, 첫 번째 요소를 제거한 후에는 나머지 모든 요소를 한 칸씩 왼쪽으로 이동시켜야 합니다.
  • 예를 들어, [a, b, c, d]에서 pop(0)을 호출하면, b, c, d를 각각 한 칸씩 왼쪽으로 이동해야 결과가 [b, c, d]가 됩니다.
• 이 이동 작업은 리스트의 길이에 비례하여 시간이 걸리므로, pop(0)은 **O(n)**의 시간 복잡도를 가집니다.

POP을 쓰되, Deque를 쓴 풀이

import collections
from typing import 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

아까 풀이에서 list를 pop(0)하여 queue의 pop처럼 가장 앞에 있는 요소를 pop했는데, 이게 O(n)이다 보니까 효율이 낮았다. 따라서 popleft()가 O(1)밖에 걸리지 않는 Deque를 사용해 개선하자는 직관이 가능하다.

슬라이싱과 정규 표현식 - 가장 효율적인 풀이

def isPalindrome(self, s: str) -> bool:
    s = s.lower()
    s = re.sub('[^a-z0-9]', '', s)
    return s == s[::-1]

아까 1차 풀이에서 문자 하나하나를 list에 append하는 대신, 정규표현식을 쓰면 위처럼 가능.

정규표현식은 추후 더 공부하자.

 

 

---

해당 글은 "파이썬 알고리즘 인터뷰(박상길)"을 공부한 내용과 책의 코드가 포함되어 있습니다.

https://github.com/onlybooks/python-algorithm-interview/tree/master