1차 시도

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\\n');

function run(input: [string, number, ...string[]]) {
  const [string, num, ...commands] = input;
  let cursor = string.length;
  let result = string;

  for (const command of commands) {
    switch (command[0]) {
      case 'L':
        if (cursor !== 0) cursor -= 1;
        break;

      case 'D':
        if (cursor !== string.length) cursor += 1;
        break;

      case 'B':
        if (cursor !== 0) {
          result = result.slice(0, cursor - 1) + result.slice(cursor);
          cursor -= 1;
        }
        break;

      case 'P':
        result =
          result.slice(0, cursor) + command.at(-1) + result.slice(cursor);
        cursor += 1;
        break;

      default:
        break;
    }
  }

  return result;
}

console.log(run(input));

• 문자열을 그대로 이용
• 시간초과 - slice를 이용한 문자열 병합이 각각 O(n)의 시간복잡도를 가짐
• 시간복잡도 O(n*m)
  • L, D = O(1)
  • B, D = O(n)
  • 명령의 길이와 주어진 스트링의 길이에 따라 최대 O(n*m)의 시간복잡도를 가진다.

개선

function run(input: [string, number, ...string[]]) {
  const [initialString, num, ...commands] = input;
  const leftStack: string[] = initialString.split('');
  const rightStack: string[] = [];

  for (const command of commands) {
    const isNotEmptyLeftStack = leftStack.length > 0;
    const isNotEmptyRightStack = rightStack.length > 0;

    switch (command[0]) {
      case 'L':
        if (isNotEmptyLeftStack) rightStack.push(leftStack.pop()!);
        break;

      case 'D':
        if (isNotEmptyRightStack) leftStack.push(rightStack.pop()!);
        break;

      case 'B':
        if (isNotEmptyLeftStack) leftStack.pop();

        break;

      case 'P':
        leftStack.push(command.at(-1)!);
        break;

      default:
        break;
    }
  }

  return leftStack.join('') + rightStack.reverse().join('');
}

• 커서의 위치를 기준으로 스택을 나눈다고 생각 (배열 이용)→ 훨씬 코드가 간결해짐
• push + reverse vs shift
  • shift는 전체 배열이 계속 재정렬되기 때문에 O(n)의 시간복잡도가 반복되어 발생
  • 마지막에만 reverse하면 한번만 재정렬하기 때문에 비교적 효울적
• 시간복잡도 O(m+n)
  • push, pop → O(1) 즉, L,D,B,P = O(1)
  • 명령의 길이와 주어진 스트링의 길이에 따라 최대 O(n + m)의 시간복잡도를 가진다.