logo
devhak

Valid Palindrome

/LeetCode

Palindrome이 뭐여... 팔린드롬... 찾아보니 회문(回文)이란다. 회문이란 앞에서부터 읽든, 뒤에서부터 읽든 동일한 단어나 문장을 의미한다. 짧게는 기러기, 이효리(?), 다시 합창합시다... 이런게 있다.
아, 로꾸거 들어보면 많이 나온다해서 들어봤는데 무슨일이야 이게...

🤦‍♀️ 나만 볼 수 없지

rokkugo

문제 해석

요약

회문인지 아닌지 판단하기! 영문과 숫자만을 고려, 대소문자 구분 없음.

전문

🇰🇷 번역

문자열이 주어지면, 회문인지 판단내려라. 오직 영숫자만을 고려하며, 대소문자는 상관하지 않는다.

주의:
이 문제를 풀기위해, 우리는 빈 문자열도 유효한 회문으로 간주한다.

Input Output
"A man, a plan, a canal: Panama" true
"race a car" false

제한 사항:
s는 글로 옮길 수 있는 ASCII 문자로만 구성된다.

🇺🇸 원문

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Input Output
"A man, a plan, a canal: Panama" true
"race a car" false

Constraints:
s consists only of printable ASCII characters.

🤔 문제 해결 방법 구상

간단하게 드는 생각으론, 하나의 포인터는 처음부터, 나머지 하나는 끝부터 시작을 하여 문자가 같으면 한칸씩 이동하면서 비교, 다르면 바로 false를 리턴하는 것이다.

  1. 주어진 문자열을 모두 소문자로 변경하고, 숫자와 문자를 제외한 문자들은 제거하여 문자열 정리(정규표현식 사용)
  2. 앞,뒤 부터 진행하는 2개의 포인터를 정의
  3. while문을 작성. 두 포인터가 만나거나 교차하기 전까지.
  4. 포인터가 가리키는 문자열을 비교하여 다르면 false 리턴, 같다면 포인터 이동
  5. while문 통과하면 true 리턴

코드 구현

/**
 * @param {string} s
 * @return {boolean}
 */
const isPalindrome = function(s) {
  s = s.replace(/[^a-zA-Z0-9]/g,'').toLowerCase();

  let forward = 0;
  let backward = s.length - 1;
  while (forward < backward) {
    if (s[forward] != s[backward]) return false;
    forward++;
    backward--;
  }

  return true;
};

결과 분석

Runtime: 84 ms
Memory Usage: 38.7 MB

시간복잡도 O(n), 공간복잡도 O(1)이다. 대체로 조건에 만족한 듯 한데, 한가지 걸리는 점은 정규표현식을 사용하며, replace 메소드를 쓴 것이다. 조건에 숫자와 영문자만을 고려하며 모두 ASCII 문자인 점을 이용해야 할 것 같다.

정규표현식은 모두 설명하기엔 힘들고, 여기서 사용한 표현만 정리하려한다.
우선 정규식 리터럴을 사용하는 방법은 슬래쉬로 감싸고 있는 /어쩌구/형태이다. 정규식에서 쓰이는 특수문자 중 [^]의 의미는 제외한 문자를 찾는 것이다. g는 전역검색을 의미한다. 즉, /[^a-zA-Z0-9]/g는 문자열 전체(g)에서 소문자 전체(a-z), 대문자 전체(A-Z), 숫자 0-9(0-9)를 제외(^)한 문자를 찾는다는 의미의 정규표현식(//)이다.

regular-expressions

정규표현식 의미

🧐 개선

ASCII는 유니코드와 마찬가지로 텍스트 이코딩의 표준이다.(유니코드가 ASCII를 본따 만들었다.) ASCII는 알파벳 대소문자와 숫자, 그리고 소량의 특수문자와 공백으로 이루어져있다. 또한 각 문자들의 ASCII 값은 특정 크기의 숫자로 이루어져 있으며, 특히 알파벳은 순서에 따라 크기가 커진다. 즉 순서 비교가 가능하다는 것이다.('a' < 'b' < 'c' < ...)

정규표현식을 쓰지 않기 때문에 따로 문자와 숫자 범위를 체크하는 함수를 만들고, 범위를 벗어나면 포인터를 이동시키도록 해야한다.

개선 코드

  1. 문자열이 2개 미만이면 무조건 true
  2. s를 소문자로 변환
  3. 문자인지 숫자이 판단하는 함수 정의
  4. 한 포인터는 앞에서부터, 나머지 포인터는 뒤에서부터 while문으로 순회하면서 3번 함수 확인해서 아니면 다음것으로 넘김
  5. 각 순서의 문자열이 다르면 바로 false 리턴
  6. while문을 통과하면 true 리턴
const isPalindrome = function(s) {
  if (s.length < 2) return true;
  s = s.toLowerCase();
  const isAlnum = (str) => {
    return ((str >= 'a' && str <= 'z') || (str >= '0' && str <= '9'));
  };
  let f = 0;
  let b = s.length - 1;

  while (f < b) {
    if (!isAlnum(s[f])) {
      f++;
      continue;
    }

    if (!isAlnum(s[b])) {
      b--;
      continue;
    }

    if(s[f] !== s[b]) return false;
    f++;
    b--;
  }
  return true;
}

개선 결과

Runtime: 88 ms
Memory Usage: 39 MB

마찬가지로 시간복잡도 O(n), 공간복잡도 O(1)이다. 복잡도만 본다면 큰 의미는 없지만, replace 메소드를 사용하지 않고, ASCII 순서를 이용하여 문제를 풀어보았다.

마무리

ASCII도 볼때마다 초면같음... 쫌 어색...ㅋㅋㅋ 저번에 풀어본 Valid Anagram비슷한가 했지만 달랐다. Valid Anagram 문제는 순서가 중요치 않아서 Map으로 구현이 가능했지만 이번엔 존재 여부보다 순서가 더 중요했기 때문이다. 또한 저번에 살펴본 유니코드와 ASCII의 차이를 살펴보았는데, 둘 다 특정 숫자로 매칭된다는 점과 순서가 있어서 비교할 수 있다는 점을 이용하여 풀 수 있다는 공통점이 있었다. 문자열 비교문제는 ASCII와 Unicode를 고려해볼 수 있다는 점을 기억하자.

Reference & Learn More

Wikipedia ASCII
MDN Unicode
MDN 정규표현식

Tags
Comments