[Javascript] 백준 6550: 부분 문자열

문제

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

입력

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

출력

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

예제 입력 1

sequence subsequence
person compression
VERDI vivaVittorioEmanueleReDiItalia
caseDoesMatter CaseDoesMatter

예제 출력 1

Yes
No
Yes
No

 

---

문제 풀이

queue를 이용하면 쉽게 풀 수 있는 문제이다. 

1. 부분 문자열인 s를 queue에 넣는다(javascript는 별도의 queue 메서드가 없으므로 스펠링으로 나누어 배열에 저장하였다. shift와 push를 이용하면 queue자료구조를 구현할 수 있다).
2. 전체 문자열인 t를 순회하며 queue의 맨앞 문자열과 같은 문자열을 만나면 queue의 맨앞 문자열을 제거해준다(shift).
3. 전체 문자열 t에 순서가 바뀌지않은 부분 문자열이 존재한다면 모두 순회했을 때 queue는 빈배열일 것이다.
4. queue가 빈배열이면 Yes, 빈배열이 아니면 No를 출력한다.

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const string = input.map((i) => i.split(" "));

for (let i = 0; i < string.length; i++) {
  const s = string[i][0];
  const t = string[i][1];

  const queueS = s.split("");

  for (spell of t) {
    if (spell === queueS[0]) {
      queueS.shift();
    }
  }

  console.log(queueS.length === 0 ? "Yes" : "No");
}