백준 9935 < 문자열 폭발 > JavaScript

📍문제 링크

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

9935번: 문자열 폭발

 

📍알고리즘 분류

- 자료구조

- 문자열

- 스택

 

📍문제 풀이

전체 문자열에서 특정 문자열(폭탄)을 제거하는데, 제거한 후에 폭탄이 남아있으면 없어질 때까지 계속 제거해야 한다

- replace 함수를 반복하면 간단히 해결될 것 같지만.. 시간초과가 발생한다

- 문자열 입력값의 길이가 100만이기 때문에, 전체 문자열을 반복해서 탐색하는 O(N^2) 복잡도로는 해결이 불가하기 때문이다

 

따라서 문제에서 힌트로 주어진 스택을 활용하여 해결해본다

 

1. 문자열에서 한 글자씩 스택에 추가한다.

2. 이 때, 스택의 길이가 폭탄 문자열의 길이 이상이면, 스택의 마지막부터 폭탄 문자열과 비교하는 것을 반복한다

(제거한 후에 또 제거해야 하기 때문)

- 비교하다가 다르면 종료

- 다르지 않으면 폭탄문자열의 길이만큼 스택에서 pop

 

📍코드 (JavaScript)

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

const input = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const word = input[0];
  const bomb = input[1];
  const stack = [];

  for (let i = 0; i < word.length; i++) {
    stack.push(word[i]);
    // 제거한 후에 또 폭탄이 생길 수 있으므로 반복
    outer: while (stack.length >= bomb.length) {
      for (let j = 0; j < bomb.length; j++) {
        if (stack[stack.length - 1 - j] !== bomb[bomb.length - 1 - j]) {
          break outer; // 없으면 아예 종료 (라벨을 활용해 바깥의 루프를 종료)
        }
      }
      // 같네?! -> 스택에서 제거
      for (let j = 0; j < bomb.length; j++) {
        stack.pop();
      }
    }
  }
  if (!stack.length) console.log("FRULA");
  else console.log(stack.join(""));
});