[백준 9935번] 문자열 폭발 - 자바스크립트(nodejs)

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

9935번: 문자열 폭발

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = [];
rl.on('line', function (line) {
  input.push(line);

  if (input.length === 2) {
    rl.close();
  }
}).on('close', function () {
  const [str, explosionStr] = input;
  console.log(solution(str, explosionStr));
});

function solution(str, str2) {
  const arr = [];

  Loop: for (let i = str.length - 1; i >= 0; i--) {
    arr.push(str[i]);

    if (arr.length >= str2.length && arr[arr.length - 1] === str2[0]) {
      for (let j = 1; j < str2.length; j++) {
        if (arr[arr.length - 1 - j] !== str2[j]) {
          continue Loop;
        }
      }

      for (let j = 0; j < str2.length; j++) {
        arr.pop();
      }
    }
  }

  if (arr.length === 0) {
    return 'FRULA';
  } else {
    return arr.reverse().join('');
  }
}

간단한 문제이고, 문자열 문제임에도 replace로 풀면 메모리 초과가 난다.

split을 이용해도 메모리 초과가 난다. 최대 100만글자이기 때문에 스택을 이용해야 메모리 초과를 피할 수 있다.

 

끝부터 배열에 넣고, 배열의 길이가 폭발 문자열의 길이 이상이고, 배열의 끝 부분이 폭발 문자열의 첫 번째 숫자와 같으면

폭발 문자열인지 비교하고, 맞으면 폭발 문자열의 길이만큼 pop해준다.

 

이렇게 되면 메모리를 피하며 효율적으로 답을 구할 수 있다!