[백준] 1406번 에디터 - JavaScript(NodeJS)

문제

1406번: 에디터

---

첫 문제 풀이

문제에서 등장하는 커서를 어떻게 구현할 것인지가 핵심이었다.

 

처음에는 커서의 위치 값 + Array.splice 함수 를 사용해보고자 했다.

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

let str = input[0].split("");
let len = input[1];
let cursor = str.length;
for (let i = 2; i < 2 + len; i++) {
  let [cmd, value] = input[i].split(" ");
  if (cmd === "L") {
    if (!cursor) continue;
    cursor--;
  } else if (cmd === "D") {
    if (cursor === str.length) continue;
    cursor++;
  } else if (cmd === "B") {
    if (!cursor) continue;
    str.splice(cursor - 1, 1);
    cursor--;
  } else if (cmd === "P") {
    str.splice(cursor, 0, value);
    cursor++;
  }
}
console.log(str.join(""));

다음과 같이 코드를 작성했고, 임의의 데이터로 크롬 콘솔 내에서 실험했을 때는 잘 작동하는 듯 보였으나
결국 정답 제출에서는 시간초과 문제로 실패했다.

---

두번째 문제 풀이

커서의 위치를 기준으로 모든 전개가 된다는 것 때문에 첫 풀이와 같은 방법을 생각했지만,
좀 더 효율적인 방법을 찾아야 했다.

 

두번째로 떠올린 해결법은 다음과 같다.

 

커서의 위치를 똑같이 잡되, 이번엔 인덱스로 커서 위치 기준을 잡을 것이 아니라
두 개의 스택들을 두고, 스택 간 경계를 현재 커서 위치라고 생각해보자.

 

두 스택 사이에 커서가 존재한다고 생각해보면

각 명령들에 대해서 코드에서는 다음과 같이 명령을 수행할 수 있을 것이다.

 

명령	수행할 명령	코드 내에서의 동작
L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)	왼쪽 스택에서 pop을 해서 오른쪽 스택에 push한다. (왼쪽 스택이 비었을 경우 명령을 수행하지 않으면 된다.)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)	오른쪽 스택에서 pop을 해서 왼쪽 스택에 push한다. (오른쪽 스택이 비었을 경우 명령을 수행하지 않으면 된다.)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임	왼쪽 스택에서 무조건 pop한다. (스택이 비어있다면 undefined를 pop하므로 별 다른 오류는 발생하지 않는다.오른쪽 스택은 건드리지 않으므로 상관이 없다.)
P $	$라는 문자를 커서 왼쪽에 추가함	왼쪽 스택에 $ 문자를 push한다.

 

모든 명령을 수행했을 때를 두 스택의 상태를 생각해보자.

 

예를 들어 정답이 12378(123커서의 위치78) 일 때,
왼쪽 스택과 오른쪽 스택으로 나눠서 표현하면

 

왼쪽 스택 = [1,2,3]
오른쪽 스택 = [8 7] 로 나타낼 수 있다.

 

오른쪽을 큐를 사용하는게 더 보기 편할 수도 있다.

 

큐를 사용하면 push/shift 메소드를 사용하게 되는데,
pop 메소드는 시간복잡도가 O(1)인데 반해, shift 메소드는 배열 맨 앞 요소를 빼야 하기 때문에 시간복잡도가 O(n)이다.

 

이러한 이유로 push, pop 메소드를 사용하는 스택을 왼쪽과 오른쪽에서 사용하기로 했다.

 

지금까지의 내용을 기반으로 코드를 작성해보자.

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let lStack = input[0].split("");
let rStack = [];
let len = parseInt(input[1]);

for (let i = 2; i < 2 + len; i++) {
  let [cmd, value] = input[i].split(" ");
  if (cmd === "L" && lStack.length) rStack.push(lStack.pop());
  else if (cmd === "D" && rStack.length) lStack.push(rStack.pop());
  else if (cmd === "B") lStack.pop();
  else if (cmd === "P") lStack.push(value);
}

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

맨 처음 두 줄은 백준에서 nodeJS를 사용할 때 입력을 받는 방법이다.

입력의 첫줄은 편집기의 문자열, 두번째는 명령어 개수, 세번째 줄부터는 수행해야 할 명령들이 나온다.

 

명령어 개수는 반드시 숫자로 타입변환하자.(우선 변환해두지 않고 사용하다 보면 다른 부분에서 오류를 찾으려 애 쓸 수도 있다.)

 

왼쪽 스택 = lStack, 오른쪽 스택 = rStack 으로 선언하였고,

for 문 안에서, if/else if 문으로 수행한 동작을 보면 위에서 표로 정리했던 내용과 같다.

 

명령을 다 마치면, join 함수를 이용해서 배열을 문자열로 바꿔준다.

 

오른쪽 스택을 처리하는 방법으로는

1. while문을 이용해 오른쪽 스택이 비어있을 때 까지 pop을 해가면서, 기존 문자열에 더해준다.

2. reverse + join 으로 요소들의 위치를 뒤집어서 문자열로 바꾼 뒤 기존 문자열에 더해준다.

 

두가지 방법 중 두번째가 깔끔한 듯 하여 두번째를 선택해서 코드를 마무리했다.

 

제출 결과

 

 

※ 알고리즘 풀이에는 정답은 없기 때문에, 더 효율적인 방법이 존재할 수 있다.