[알고리즘] 6550. 부분 문자열(JS)

🌟 문제

문제
2개의 문자열 s와 t가 주어졌을 때 s가 t의 부분 문자열인지 판단하는 프로그램을 작성하라. 부분 문자열을 가지고 있는지 판단하는 방법은 t에서 몇 개의 문자를 제거하고 이를 순서를 바꾸지 않고 합쳤을 경우 s가 되는 경우를 이야기 한다.

입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문자열 s 와 t가 빈칸을 사이에 두고 들어온다. s와 t의 길이는 10만을 넘지 않는다.

출력
입력된 s와 t의 순서대로 s가 t의 부분 문자열인 경우 Yes라 출력하고 아닐 경우 No라고 출력한다.

백준 - 부분 문자열

풀이 방법 및 코드

---

풀이 방법

1. 입력을 s와 t로 분리한다.
2. t에 s가 포함되어 있는지 검사한다. 포함되어 있다면 "Yes"를 리턴한다.
3. 포함되어 있지 않다면, s를 단어로 쪼개어 다시 검사한다.
4. isValidate()에서 s의 분리된 단어들이 t에 포함되어 있는지 검사한다.
5. 존재한다면, 해당 단어의 다음 인덱스부터 저장하여 다음 단어를 검사한다.

/**
 * 6550. 부부 문자열
 * https://www.acmicpc.net/problem/6550
 */

const isValidate = (words, t) => {
  let tmp = t;
  for (let word of words) {
    if (tmp.indexOf(word) == -1) {
      return false;
    } else {
      tmp = tmp.substr(tmp.indexOf(word) + 1);
    }
  }
  return true;
};

const solution = (line) => {
  let answer = "";
  const [s, t] = line.split(" ");

  // 부분 문자열이라면
  if (t.includes(s)) {
    return "Yes \n";
  } else {
    // 하나씩 검사
    const words = s.split("");
    return isValidate(words, t) ? "Yes \n" : "No \n";
  }
};

마무리

최근에 코딩 테스트를 보면서 아쉬웠던 문제가 있었다. 그래서 백준에서 비슷한 유형의 문제를 찾아 풀어보고 싶었다.