[LeetCode] 125. Valid Palindrome

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

Valid Palindrome - LeetCode

 

Problem:

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

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

---

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

 

Constraints:

• 1 <= s.length <= 2 * 10^5
• s consists only of printable ASCII characte

---

코드에 들어가야 할 것

1. 대소문자 구분하지 않는다 → 입력받은 문자열을 다 소문자로 바꿔야 한다.

2. 영문자와 숫자만을 대상으로 한다 → 영문자와 숫자에 해당하는가를 판별해야한다.

내가 작성한 코드

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s1 = s.lower()
        s1 = ''.join(c for c in s1 if c.isalnum())
        num = len(s1) // 2
        for a in range(num):
            if s1[a] != s1[-1-a]: return False
        return True

 

---

[풀이 1] 리스트로 변환

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = []
        for c in s:
            if c.isalnum():
                strs.append(c.lower())
                
        # 팰린드롬 여부 판별
        while len(strs) > 1:
            if strs.pop(0) != strs.pop(): return False
        return True

파이썬의 리스트는 pop() 함수에서 인덱스를 지정할 수 있기 때문에, 이처럼 0을 지정하면 맨 앞의 값을 가져올 수 있다. 이렇게 맨 뒷부분의 pop() 결과와 매칭해 나가면서 일치하지 않는 경우 False를 리턴한다. 

 

문제점

1. 속도가 느리다(229ms)

 

 

[풀이2] 데크 자료형을 이용한 최적화

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 자료형 데크로 선언
        strs: Deque = collections.deque()
            
        for c in s:
            if c.isalnum():
                strs.append(c.lower())
                
        while len(strs) > 1:
            if strs.popleft() != strs.pop(): return False
        return True

자료형을 Deque로 선언하는 것만으로 실행 속도가 5배 넘게 개선되었다.

리스트의 pop(0)은 O(n)이지만 데크의 popleft()는 O(1)이기 때문이다.

문자열이 길어짐에 따라 이를 n번씩 반복하면 리스트 구현은 O(n^2), 데크 구현은 O(n)으로 성능 차이가 크다.

 

변수 strs를 선언할 때 자료형이 Deque라는 것을 명시적으로 알 수 있도록 하는 친절한 코드!

 

 

[풀이 3] 슬라이싱 사용

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        # 정규식으로 불필요한 문자 필터링
        s = re.sub('[^a-z0-9]', '', s)
        
        return s == s[::-1]

정규표현식 (Regular expressions) 은 특정한 규칙을 가진 문자열의 집합을 표현하는 데 사용하는 형식 언어이다. 

re.sub(): 문자열에서 정규 표현식과 일치하는 부분에 대해서 다른 문자열로 대체한다.

[^a-z0-9]: 소문자 알파벳, 숫자를 제외한 문자만 매치한다.

따라서 문자열 s에서 소문자 알파벳, 숫자를 제외한 문자들만 ('')으로 대체하는 방식으로 문자를 필터링한다.
is.alnum()을 사용해 문자를 일일이 점검하지 않아도 된다.

 

[::-1]을 사용하면 문자열을 뒤집을 수 있다.

 

책에서와 달리 나는 속도가 개선되지 않았다. 하지만 책에서는 속도를 여러 번 실행한 결과의 중앙값을 사용한 거라 다를 수도 있을 것 같다.

 

 

[풀이 4] C 구현

bool isPalindrome(char* s) {
    int bias_left = 0;
    int bias_right = 1;
    
    int str_len = strlen(s);
    for (int i = 0; i < str_len; i++) {
        // 스킵 포인터 처리
        while(!isalnum(s[i+bias_left])) {
            bias_left++;
            if(i+bias_left == str_len)
                return true;
        }
        
        while(!isalnum(s[str_len - i - bias_right])) {
            bias_right++;
        }
        
        if (i + bias_left >= str_len - i - bias_right)
            break;
        
        if (tolower(s[i + bias_left]) != tolower(s[str_len - i - bias_right]))
            return false;
    }
    
    return true;
}

필터링해야 하는 문자는 bias_left, bias_right 변수를 이용해 한 칸씩 건너뛰는 형태로 처리했다.

모든 기능을 직접 구현하다 보니 코드는 길어졌지만 실행 결과가 5ms라는 놀라운 속도를 보인다.

역시 C와 같은 컴파일 언어는 파이썬 같은 인터프리터 언어에 비해 더욱 좋은 성능을 낸다는 사실을 확인할 수 있다.

---

문자열 슬라이싱

파이썬에서 제공하는 문자열 슬라이싱 기능은 매우 편리하며 내부적으로 굉장히 빠르게 동작한다. 위치를 지정하면 해당 위치의 배열 포인터를 얻게 되며 이를 통해 연결된 객체를 찾아 실제 값을 찾아내는데, 이 과정은 매우 빠르게 진행된다.

문자열을 별도로 리스트로 매핑하는 등의 처리는 데이터 구조를 다루는 입장에서는 좋은 방법이지만, 추가적인 연산 비용이 필요하므로 속도에서는 손해를 볼 수 있다.

 

요약

1. 대소문자 구분하지 않는다 → 입력받은 문자열을 다 소문자로 바꿔야 한다 → .lower()

2. 영문자와 숫자만을 대상으로 한다 → 영문자와 숫자에 해당하는가를 판별해야 한다. → .isalnum() / 정규표현식 활용

3. 가장 앞 원소를 pop할 때 리스트보다 데크에서 실행 속도가 더 빠르다

4. 문자열 슬라이싱 [::-1]을 통해 문자열을 쉽고 빠르게 뒤집을 수 있다.

 

 

이 글은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.