[백준][스택] 1406 에디터 NodeJs 구현

     

목차

 

 

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

문제

 

 

 

 

 

문제 구현 방향

처음에 slice로 문자열 붙여 넣기하고 자르기 해서 시간초과로 인해 틀렸다..

그 이유는 slice는 O(N)의 시간 복잡도를 가지기 때문이다.

 

 

 

올바른 문제풀이

당연히 자료구조로 풀면 풀린다. js메서드로 shift연산은 O(N)의 시간복잡도를 가지므로 스택을 사용해 풀었다.

커서를 기준으로 왼쪽 스택, 오른쪽 스택이 있다고 생각하면 쉽게 풀린다. (이걸 떠올리는게 어렵다..)

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let lStack = input[0].trim().split("");
let rStack = [];
let idx =2;

while(idx < input.length){
  let order = input[idx].trim().split(" ");
  if(order[0] === 'P'){
    lStack.push(order[1]);
  }
  else if(order[0] === 'L'){
   if(lStack.length)rStack.push(lStack.pop());
  }
  else if(order[0] === 'D'){
    if(rStack.length)lStack.push(rStack.pop());
  }
  else if(order[0] === 'B'){
    lStack.pop();
  }
  idx++;
}

let answer  = lStack.join("");
answer += rStack.reverse().join("");
console.log(answer);