백준 9935 문자열 폭발 | JavaScript 스택

https://www.acmicpc.net/problem/9935

---

이제 어느정도 스택 문제를 푸는 것에 익숙해진 것 같아서 정답률 27%의 골드 문제에 도전했다.🥸

주어진 문자열 내에 폭발 문자열이 포함되어있으면 폭발문자열을 제거하고, 폭발 문자열의 앞 뒤 문자열을 이어 새로운 문자열을 만들면 된다.
이전에 풀던 문제들처럼 스택에 값을 넣다가 폭발 문자열과 같아지면 pop하면 되지만,,
첫 문자열부터 비교하는 것은 효율이 좋지 않을 것이다.

예를 들어, 폭발 문자열의 길이가 10인데, 9번째자리까지는 같고 10번째 문자만 다르다면 총 10번의 비교를 하고서야 폭발하지 않는다는 것을 알 수 있다.

그래서 우선은 스택에 계속 push하고, 마지막 문자를 비교하기로 했다. 마지막 문자가 같다면 스택에서 bomb의 길이만큼 slice하여 같은지 비교해보면 된다 !!

if (
      stack[stack.length - 1] == bomb[bomb.length - 1] &&
      stack.slice(stack.length - bomb.length).join("") == bomb
    )

마지막 문자가 다른 경우에는 두번째 조건을 확인하지 않고 넘어가니 slice, join 연산도 최소화할 수 있다. 원본 스택이 변경되면 안 되기 때문에 꼭! slice를 사용해야한다.

for (let j = 0; j < bomb.length; j++) {
        stack.pop();
      }

만약 같은 경우에는 폭발 문자열의 길이만큼 pop을 반복해주면 된다. 이건 단순 반복문이 최선인 것 같다🥲

---

전체 코드

const stack = [];

function solution(string, bomb) {
  for (let i = 0; i < string.length; i++) {
    stack.push(string[i]);

    if (
      stack[stack.length - 1] == bomb[bomb.length - 1] &&
      stack.slice(stack.length - bomb.length).join("") == bomb
    ) {
      for (let j = 0; j < bomb.length; j++) {
        stack.pop();
      }
    }
  }

  return stack.length == 0 ? "FRULA" : stack.join("");
}

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", (line) => {
  input.push(line);

  if (input.length === 2) {
    rl.close();
  }
}).on("close", () => {
  const string = input[0];
  const bomb = input[1];

  console.log(solution(string, bomb));
});