boj 1406 javascript

원본 배열의 인덱스를 활용하여 수정하는 방식은 주어진 배열의 길이 만큼의 추가 연산이 들어가기 때문에

요소를 추가할 때 unshift, splice를 활용하면 O(N)이 추가된다.

시간 복잡도를 최소화하기 위하여 2개의 배열과 push, pop O(1) 메서드를 활용해 함수를 만들었다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const left = input[0].split('');
const right = [];

for (let i = 0; i < parseInt(input[1]); i++) {
  const command = input[i + 2].split(' ');
  switch(command[0]) {
    case "L":
      const leftEl = left.pop();
      leftEl && right.push(leftEl);
      break;
    case "B":
      left.pop();
      break;
    case "D":
      const rightEl = right.pop();
      rightEl && left.push(rightEl);
      break;
    case "P":
      left.push(command[1]);
      break;
    default:
      break;
  }
}

console.log(left.concat(right.reverse()).join(''));