[백준] 1406 | 에디터 | 자바스크립트

문제

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

 

정답 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";

const input = fs.readFileSync(filePath).toString().trim().split("\n");

function solution(input) {
  const initialString = input[0];
  const commands = input.slice(2);

  // 스택 두개 초기화
  const leftStack = initialString.split("");
  const rightStack = [];

  for (const command of commands) {
    const [cmd, char] = command.split(" ");

    switch (cmd) {
      case "L":
        if (leftStack.length > 0) {
          rightStack.push(leftStack.pop());
        }
        break;
      case "D":
        if (rightStack.length > 0) {
          leftStack.push(rightStack.pop());
        }
        break;
      case "B":
        if (leftStack.length > 0) {
          leftStack.pop();
        }
        break;
      case "P":
        leftStack.push(char);
        break;
    }
  }

  return leftStack.concat(rightStack.reverse()).join("");
}

console.log(solution(input));

두 개의 스택을 사용했다. 스택은 요소 삽입 삭제의 시간 복잡도가 O(1) 로 매우 빠르다. 따라서 해당 방법으로 시간제한을 통과하도록 구현할 수 있었다. 

• leftStack : 커서 왼쪽에 있는 문자 저장
• rightStack : 커서 오른쪽에 있는 문자 저장
• rightStack.reverse() : 오른쪽 스택의 문자의 순서를 뒤집어서 순서 조정

 

시간복잡도

• 각 스택의 push/pop : O(1)
• reverse() : O(N)
• 총 시간 복잡도는 O(M + N) 

 

풀이

첫 번째 시도 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";

const input = fs.readFileSync(filePath).toString().split("\n");

function solution(input) {
  const strArr = input[0].split("");

  let cursor = strArr.length; // 커서 초기 위치

  for (let i = 2; i < input.length; i++) {
    const command = input[i].split("");

    switch (command[0]) {
      case "L":
        if (cursor > 0) {
          cursor--;
        }
        break;
      case "D":
        if (cursor < strArr.length) {
          cursor++;
        }
        break;
      case "B": // 왼쪽 삭제
        if (cursor > 0) {
          strArr.splice(cursor - 1, 1);
          cursor--;
        }

        break;
      case "P":
        strArr.splice(cursor, 0, command[2]);
        cursor++;
        break;
    }
  }

  return strArr.join("");
}

console.log(solution(input));

처음에 구현한 코드가 시간 초과가 발생했다. 시간 초과의 원인을 분석하고 시간 제한을 만족시키기위한 해결 방법을 찾아보았다.

 

시간 초과 원인

splice() 사용한 것에 문제가 있다.

• 배열의 특정 위치에 문자를 추가/삭제 하기 위해서 splice() 메서드를 사용했다.
• splice() 는 배열의 크기 N 에 비례한 시간복잡도 O(N) 을 가진다. 따라서 배열의 크기가 클수록 실행 시간이 급격히 늘어난다.

 

문제 조건은 다음과 같았다.

• 최대 명령어 개수 : M = 500,000
• 최대 문자열 길이 : N = 100,000
• 최악의 경우 O(M x N) 의 시간복잡도를 가진다.

 

시간 복잡도 계산

• O(M x N) = 500,000 x 100,000 = 50,000,000,000 (500 억 번의 연산)
• 문제의 시간 제한은 0.3 이다. 보통 1초에 약 1억번 연산이 가능한것을 보았을 때, 해당 코드는 500억 번의 연산을 요구하므로 최대 500초가 걸려서 시간 초과가 발생한다.

 

시간 제한 내 문제를 해결하려면

• 0.3초 : 100,000,000 x 0.3 = 30,000,000 이므로 최대 30,000,000 연산을 넘지 않아야한다.
• 두 개의 스택을 사용하여 요소 추가/삭제를 O(1) 시간복잡도로 처리할 수 있도록 해야한다.
• 커서를 중심으로 문자열을 왼쪽 스택과 오른쪽 스택으로 나누어 처리하면, 커서 이동 및 문자 추가/삭제 작업을 모두 빠르게 수행할 수 있다.