🟢[Leet code - 125] Valid Palindrome ✅

Valid Palindrome - LeetCode

문제

• Input
  문자열 s
• Output
  s에서 영, 숫자만 남기고, 모두 소문자로 변경한 문자열이 Palindrome인지에 대한 bool 값
  ※ Palindrome : 거꾸로 읽어도 같은 단어
• Constraints
  s의 원소는 모두 아스키문자에 속한다.

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

| O(1) : 크게 상관없음 | O(log n) : 크게  상관없음 | O(n) :  100'000'000 (1억) | O(n log n) : 1'000'000 (100만) | O(n^2) : 10'000 (1만) |

---

 

$1 \le n \le 200'000$으로 $O(n \log n)$ 부터 고려할 수 있다.

 

 

해결 과정

문자열s의 필터링 후 반복문에서 앞, 뒤로 같은지 확인하면 된다.

아래와 같은 수도코드를 먼저 작성해봤었다.

//필터링
for 0 <= i < n
{
    IF (s[i] == 영,숫자아니면) 제거 + continue;
    IF (대문자면) 소문자로
}

// 검사
FOR 0 <= i < (new n/2)
{
    IF (s[i] != s[new n - i - 1]) return false;
}

return true;

해당 풀이는 대략 $n + (n/2)$로, $O(n)$의 풀이라고 볼 수 있다.

 

 

구현

처음에는 조건에 맞지 않은 문자를 제거하려고 했었지만,

배열에서의 삭제는 성능이 좋지 못하니까 조건에 맞는 문자를 새로운 배열에 넣기로 변경했다.

bool isPalindrome(string s) 
{
    string newS;
    newS.reserve(s.size());

    for (char d : s)
    {
        d = tolower(d);
        if (isalpha(d) || isdigit(d)) newS.push_back(d);
    }

    int r = newS.size();
    for (int l = 0; l < newS.size() / 2; ++l)
    {
        if (newS[l] != newS[--r]) return false;
    }

    return true;
}

 

 

되돌아보기

간단한 문제여서 금방 풀었지만, 가져가야 할 디테일들이 몇 있었다.

tolower, isalpha, isdigit는 unsigned char 캐스팅으로

이런 함수들은 음수 값이 들어오면 에러가 아니라 정의되지 않은 동작이 발생할 수 있다.
그렇기 때문에 unsigned char를 이용하여 사용하는 것이 안전하다.

unsigned char uc = static_cast<unsigned char>(c);
isalnum(uc);// 안전

이 문제에서는 아스키코드 내에서 입력이 나오기 때문에 괜찮긴 하다!

 

isalnum

문자와 숫자를 한 번에 확인 가능한 함수가 있었다;

 

조금 더 다양한 사고

필터링 후 회문(Palindrome)인지 확인하려는 생각은 좋았는데, 필터링하지 않고 바로 회문인지에 대한 체크가 가능했나?

까지 했었으면 더 좋았을지도? 모르겠다.

 

자세히는 필터링 과정을 따로 배열에 담아야 하는가? 이런 생각을 해보았다면 공간적으로 더 나은 코드를 작성했을지도 모른다.

 

 

개선 코드

필터링과 회문을 같이 체크하는 코드로, 시간복잡도면에서 $n / 2 $만큼 줄일 수 있고, 공간복잡도도 O(1)로 줄일 수 있다.

bool isPalindrome(string s) 
{
    int l = -1;
    int r = s.size();

    // 한 번은 r <= l 인 상황이 오는데 답에 영향이 없기 때문에 상관 없다.
    while (l < r)
    {
        // l 찾기
        while (l < r && isalnum(s[++l]) == false){};
        s[l] = tolower(s[l]);

        // r 찾기
        while (l < r && isalnum(s[--r]) == false){};
        s[r] = tolower(s[r]);

        // 비교
        if (s[l] != s[r]) return false;
    }
    return true;      
}