Skip to main content

03. 문자열 탐색

문자열 탐색​

어떤 문자열 S에서, 어떤 패턴 P를 찾아내는 알고리즘이다. 문자열 집합에서 어느 한 개의 문자열을 탐색하는 알고리즘은 Trie나 이진 탐색을 참고하길 바란다. [나무위키]

사실 해당 문자열 탐색 알고리즘으로 유명한 KMP, Rabin 등이 있지만 해당 섹션에서 하지 않았기에 다음에 다루어봐야겠다.

문자에 관련된 문제여서 그런지 정규식을 이용한 문제가 많다. (정규식 공부 꾸준히 하자....)

문제 풀이​

Ch.03 - 01. 회문 문자열​

function solution(str) {
  const convertToUpperStr = str.toUpperCase();

  const n = convertToUpperStr.length;
  const limitNum = Math.floor(n / 2);

  for (let i = 0; i < limitNum; i++) {
    if (convertToUpperStr[i] !== convertToUpperStr[n - 1 - i]) return "NO";
  }

  return "YES";
}

Ch.03 - 02. 유효한 팰린드롬​

function solution(str) {
  const cleanStr = str.replace(/[^a-zA-z]/g, "").toUpperCase();

  return cleanStr === cleanStr.split("").reverse().join("") ? "YES" : "NO";
}

Ch.03 - 03. 숫자만 추출​

function solution(str) {
  return Number.parseInt(str.replace(/[^0-9]/g, ""), 10);
}

Ch.03 - 04. 가장 짧은 문자거리​

function solution(str, char) {
  let cacheDistance = 100;
  let answer = new Array(str.length).fill(0);

  for (let i = 0; i < str.length; i++) {
    cacheDistance = str[i] === char ? 0 : ++cacheDistance;

    answer[i] = cacheDistance;
  }

  for (let i = str.length - 1; 0 <= i; i--) {
    cacheDistance = str[i] === char ? 0 : Math.min(++cacheDistance, answer[i]);

    answer[i] = cacheDistance;
  }

  return answer;
}

이 문제의 핵심은 앞에서 한번 뒤에서 한번 양쪽으로 한번씩 순회 하면서 값을 비교 하는 것이다.

Ch.03 - 05. 문자열 압축​

function solution(str) {
  let answer = "";
  let cache = "";

  for (let i = 0; i <= str.length; i++) {
    const targetChar = cache[0];
    const curChar = str[i];

    if (cache === "" || targetChar === curChar) {
      cache += curChar;
    } else {
      answer += `${targetChar}${1 < cache.length ? cache.length : ""}`;
      cache = curChar;
    }
  }

  return answer;
}