[알고리즘/Python] LeetCode 125. Valid Palindrome

📑 1. 문제 이해

https://leetcode.com/problems/valid-palindrome/?envType=study-plan-v2&envId=top-interview-150 

Valid Palindrome - LeetCode

이 문제는 주어진 주어진 문자열을 조건에 맞춰서 조작한 후 그 문자열이 팰린드롬인지 판별하는 문제 입니다. 

 

☑️ 테스트케이스

문제에서 주어진 테스트를 분석해보면 다음과 같습니다.

 

1) Example1 : "A man, a plan, a canal: Panama" 

    - 영문자(대, 소문자)와 특수문자(, :)로 이루어진 문자열. 조건에 맞춰 문자열을 조작한 결과(amanaplanacanalpanama)의 문자 갯수가 21자로 홀수개.

2) Example 2 : "race a car":

   -  영문자로만 이루어지고,  짝수개(8개) 문자로 이루어짐.

3) Example 3 : " "

  - 빈 문자열. 문제의 제한조건에서 문자열의 길이가 1이상이라고 했지만 blank도 아스키 코드로 하나의 문자입니다.

 

이에 더해서 제가 생각해본 테스트케이스는 다음과 같습니다.

 

4) "OP" : 숫자와 문자열로 이루어진 짝수길이의 문자열.

5) ".," :  특수문자로만 이루어진 문자열.

💡 2. 알고리즘 설계

 문제를 처음 봤을때 앞에서 부터 i번째 문자와 뒤에서부터 i번째 문자를 쌍으로 비교해야한다는 점에서 투포인터를 떠올릴 수 있었습니다. 문자열을 반으로 나누어서 앞부분을 가리키는 포인터와 뒷부분을 가리키는 포인터 두개를 사용하여 비교한다면 팰린드롬을 판별할 수 있습니다.

 

1. 먼저 문자열 s를 순회하면서 알파벳인 혹은 숫자인 문자만 골라서 새로운 문자열을 만듭니다. 이때 알파벳인 경우 소문자로 대치해줍니다.

2. 새로운 문자열의 절반까지만 순회하면서 앞에서 i번째인 문자열과 뒤에서 i번째인 문자열을 쌍으로 비교합니다. 이때 같지 않은 경우가 한번이라도 등장한다면 팰린드롬이 아니므로 False를 반환합니다. 이때 문자열의 길이와 상관없이 처음부터 인덱스 len(s) // 2 -1까지 검사하게 됩니다.

    - 문자의 개수가 짝수개인 경우 인덱스 (문자열의 길이 // 2) 는 다음 그림과 같이 절반 뒷부분의 시작 문자가 됩니다. 따라서 처음부터 인덱스 len(s) // 2 - 1까지가 문자열의 절반에 해당됩니다.

    - 문자의 개수가 홀수개인 경우  인덱스 (문자열의 길이 // 2) 다음과 같이 정 가운데 문자가 됩니다. 정 가운데 문자를 제외하고 문자열을 앞부분과 뒷부분으로 대칭적으로 나눌 수 있습니다. 따라서 처음부터 인덱스 len(s) // 2 - 1까지 검사하게 됩니다.

 

3. for문이 끝났다면 True를 반환합니다. 한번도 서로 다른 쌍의 문자열이 등장하지 않았다면 팰린드롬이라고 판단합니다.

def isPalindrome(s: str):
    new_s = []
    for c in s:
        if c.isalpha():
            new_s.append(c.lower())
        elif c.isnumeric():
            new_s.append(c)

    for i in range(len(new_s) // 2):
        left, right = new_s[i], new_s[-i - 1]
        if left != right:
            return False
    return True

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 영문자와 숫자로만 이루어진 새로운 문자열을 만들기 위해 전체 문자열을 순회하는데 O(N) 시간이 필요합니다. 팰린드롬 판별을 위해 새로운 문자열의 절반을 순회하면서 쌍으로 문자열을 비교하는데 최대 O(N) 시간이 필요합니다.  따라서 총 시간 복잡도는 O(N)이 됩니다. 

공간 복잡도: O(N). 영문자와 숫자로만 이루어진 새로운 문자열을 저장하기 위한 추가 공간이 필요합니다. 최악의 경우 기존의 문자열와 똑같은 새로운 문자열이 만들어지므로 공간복잡도는 O(N)이 됩니다.

 

⚒️ 3. 최적화

 배열을 한번만 순회하면서 문자열 조작과 문자열 비교를 동시에 처리할 수 없을까 생각해보았습니다.  하지만 이 경우에는 반복문 안에서 start, end 포인터 각각이 알파벳 혹은 숫자가 될때까지 인덱스를 조정하는 반복문이 또 필요합니다. 이때, Index Out of Range 예외가 발생할 가능성이 높습니다. 또,  1) start 포인터가 end 포인터보다 오른쪽으로 이동하지 않도록 체크해야하고 2) start, end 포인터가 배열의 범위를 벗어나지 않도록 체크해야하고3) ".," 혹은 " "와 같이 특수한 경우에도 팰린드롬으로 판별할 수 있도록 해야하는 등 매번 체크해야하는 것이 늘어나 오히려 연산의 횟수가 더 늘어날 수 있습니다.

 따라서 이 경우에는 문자열 조작을 끝낸 후, 새로운 문자열을 대상으로 문자열을 비교하는 것이 좋다고 생각됩니다.

 ⎌ 4. 검토

 테스트 케이스들을 검토해보겠습니다.

 

1) Example1 "A man, a plan, a canal: Panama" 

    - 영문자(대, 소문자)와 특수문자(, :)로 이루어진 문자열. 조건에 맞춰 문자열을 조작한 결과 길이가 21인 amanaplanacanalpanama 이 됩니다. 이 문자열을 정가운데 문자 'c'를 기준으로 amanaplana + c + analpanama와 같이 나눌 있고, 앞부분과 뒷부분의 문자열을 쌍으로 비교시 같기 때문에 팰린드롬으로 판별됩니다. 따라서 두번째 for문을 빠져나와서 True가 반환됩니다.

 

2) Example 2: "race a car"

   -  첫번째 for문에 의해 문자열 조작된 결과는 raceacar이 되고, 이는 race + acar 로 나누어집니다. 4번째 문자 'e' 와 뒤에서 4번째 문자 'a'가 같지 않기 때문에 팰린드롬이 아니라고 판별되며 False가 반환됩니다.

 

3) Example 3: " "

  - 공백이 제거된 빈 문자은 길이가 0으로 두번째 for문에 진입하지 않기 때문에 바로 True가 반환됩니다. 

 

4) "OP" : 숫자와 문자열로 이루어진 짝수길이의 문자열.

    - 두번째 for문에 의해 False가 반환됩니다.

 

5) ".,": 특수문자로만 이루어진 문자열.

    - 특수문자가 제거된 빈 문자은 길이가 0으로 두번째 for문에 진입하지 않기 때문에 바로 True가 반환됩니다. 

 

---

🤔 다른 사람의 풀이

python의 리스트 comprehensing 문법을 사용하여 가독성을 높일 수 있습니다. 또한, 앞의 문자열과 뒤의 문자열을 비교할때 비트 연산자 ~ 를 사용하여 더 간단히 나타낼 수 있습니다.

 

 비트 연산자 ~는 NOT을 의미하며  비트를 반전시키는 연산을 의미합니다. 정수 x의 ~x 결과는 (-x -1)을 나타내는 연산입니다. 컴퓨터가 음수를 표현하기 위해 사용하는 2의 보수 연산에서 ~x = -x-1 도출할 수 있습니다.  -x = ~ x + 1로 나타낼 수 있고 여기서, + 1을 왼쪽항으로 옮기면 ~x = -x -1임을 확인할 수 있습니다.

 

~x = -x - 1 임을 응용해서 앞에서 i번째 글자와 대응되는 뒤에서 i번째 글자를 구하기 위해 비트 연산자 ~을 사용할 수 있습니다.

x	~x
0	-1
1	-2
2	-3
3	-4

 리스트 comprehensing 문법과 비트 연산자 ~을 사용하여 문제를 푼 코드는 다음과 같습니다.

def solution2(s: str):
    s = [c.lower for c in s if c.isalnum()]

    for i in range(len(s) // 2):
        left, right = s[i], s[~i]
        if left != right:
            return False
    return True

 

 

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 리스트 comprehensing 하는 것도 for문을 순회하는 것과 같은 연산이라고 볼 수 있습니다.

공간 복잡도: O(N). 리스트 comprehensing 결과를 저장하는 새로운 문자열을 위한 공간이 필요합니다.

 

---

✅  정리

◎ 비트 연산자 ~ 는 비트를 반전시킨 결과이며 그 값은 (-x-1)과 같다. 이를 응용해서 nums[i]와 대응되는 쌍, nums[-i-1]을 구할 수 있다.