[BEAKJOON / node.js] 9935 문자열 폭발

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

//test.txt
mirkovC4nizCC44
C4

---

sol1

let input = require('fs').readFileSync('test.txt').toString().trim().split('\n');
let arr = input[0];
let bomb = input[1];
let bomLen = bomb.length;
let stack = [];
let top = 0;

for(let i=0;i<arr.length;i++) {
  stack.push(arr[i]);
  top = arr[i]
  if(top === bomb[bomLen-1]) {
    let last = stack.slice(-bomLen);
    if(last.join('') === bomb) stack.splice(-bomLen)
  }
}
console.log(stack.length? stack.join(''):'FRULA');
//mirkovniz

스택을 이용해 해결할 수 있는 문제였다. slice와 splice를 사용했기 때문에 속도가 많이 느릴 줄 알았는데 생각보다 빠르게 나왔다.
스택에 요소가 들어올 때마다 폭탄 문자열의 마지막 문자와 같은 지 비교한다. 만약 폭탄의 마지막 문자와 같다면, 스택에서 폭탄 문자열 길이만큼을 꺼낸 후 꺼낸 문자열과 폭탄 문자열이 같다면 제거한다. 폭탄 문자열의 마지막 문자와 비교하기 때문에 입력처럼 'CC44'로 받아도 연속으로 제거 가능하도록 할 수 있다.

1. [C]

2. [CC]

3. [C]
	CC4 가 되면서 마지막 문자인 4 와 폭탄의 마지막 문자인 4가 같아짐
	if문에 들어가서 폭탄문자열인 2만큼 스택에서 때온다음 비교
	C4 === C4 가 되면서 제거
    
4. [] 다시 4가 들어와 C4가 되면서 if문에 걸리고 3. 을 반복하면서 제거된다.

 

1.

for(let i=0;i<arr.length;i++) {
  stack.push(arr[i]);
  top = arr[i]
 }

스택에 하나씩 담을 수 있는 for문을 만들고,  마지막에 들어온 요소와 폭탄의 마지막 글자를 비교하기 위해 top을 따로 저장해둔다. 별도로 저장하지 않고 stack[stack.length-1]로 받아도 되지만, 매번 배열의 길이를 찾아야 하기 때문에 top을 저장하는 편이 빠를 것이다.

 

2.

  if(top === bomb[bomLen-1]) {
    let last = stack.slice(-bomLen);
    if(last.join('') === bomb) stack.splice(-bomLen)
  }

스택에 들어온 문자와 폭탄 문자열의 마지막 문자가 같다면, 첫 번째 if문에 걸리게 된다. last에 현재 스택에서 폭탄의 길이만큼 잘린 배열이 담기게 되며, join을 사용해 다시 문자열로 만든 뒤 폭탄 문자열과 비교한다. 만약 같다면 스택에서 폭탄의 문자열 길이만큼 제거한다.