[백준] 9935 문자열 폭발 - javascript

📌 문제

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

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let str = input[0].trim();
let explode_str = input[1].trim();
let len = explode_str.length;
let stack = [];
for (let i = 0; i < str.length; i++) {
  let flag = false;
  if (str[i] === explode_str[len - 1]) {
    for (let j = 0; j < len - 1; j++) {
      if (stack[stack.length - (j + 1)] === explode_str[len - (j + 2)]) {
        continue;
      }
      flag = true;
      break;
    }
    if (flag) {
      stack.push(str[i]);
    } else {
      for (let k = 0; k < len - 1; k++) {
        stack.pop();
      }
    }
  } else {
    stack.push(str[i]);
  }
}
let result = stack.join("");
if (result === "") {
  console.log("FRULA");
} else {
  console.log(stack.join(""));
}

✔ 알고리즘 : 스택

✔ 주어진 문자열에서 폭발 문자열을 제거하는 문제

✔ 문자열을 순회하며 현재 인덱스의 문자가 폭발문자열의 끝문자와 같은지 비교

✔ 같으면 폭발문자열의 index[(폭발문자열의 길이-2)] ~ index[0] 와 현재 stack의 상단부터 비교

✔ index 0 전에 같지 않은 index가 나오면 flag바꿔주고 break

✔ flag가 true 인 경우
현재 스택과 폭발문자열을 비교했을 때 폭발문자열이 포함되어 있지 않는 경우이므로 현재 인덱스의 문자 stack에 push

✔ flag가 false 인경우
현재 스택과 폭발문자열을 비교했을 때 폭발문자열이 포함되어 있는 경우이므로 폭발문자열의 길이-1만큼 pop 반복

✔ 마지막에 스택 join했을 때 빈 문자열이면 모두 없어진 상태이므로 FRULA 출력 , 빈 문자열이 아니면 그대로 출력

✔ 난이도 : 백준 기준 골드 4