상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.
출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.
자바스크립트의 replace 함수와 정규식을 이용해 풀이할 경우, n의 크기로 인해 메모리 초과가 난다.
stack을 이용한 풀이
stack의 index를 가리키는 idx 변수를 이용하여 stack[idx]에 문자열을 넣는다.
stack의 끝 문자열과 폭발 문자열 exploe의 끝 문자열이 일치하면, 폭발 문자열인지 확인한다.
문자열이 일치하면(폭발 문자열이라면) idx를 exploe.length만큼 앞으로 이동한다.
폭발이 끝난 문자열을 0번 index부터 idx만큼 slicing한 결과가 남은 문자열이다.
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");
const str = input[0].trim();
const exploe = input[1].trim();
let n = exploe.length;
let stack = new Array(str.length).fill("");
let idx = 0;
for (let i=0; i<str.length; i++) {
// 1. stack에 새로운 문자열을 넣는다.
stack[idx++] = str[i];
// 2. stack의 가장 뒤에 있는 문자열이 폭발 문자열과 일치하면 pop한다.
// (index를 이전으로 이동한다.)
if (stack[idx-1] === exploe[n-1] && idx > n-1) {
let flag = true;
for (let j=1; j<n; j++) {
if (stack[idx-1-j] != exploe[n-1-j]) {
flag = false;
break;
}
}
if (flag) {
idx -= n;
}
}
}
let result = stack.slice(0, idx).join("");
if (result === "") console.log("FRULA");
else console.log(result);