문제
첫 문제 풀이
문제에서 등장하는 커서를 어떻게 구현할 것인지가 핵심이었다.
처음에는 커서의 위치 값 + 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 으로 요소들의 위치를 뒤집어서 문자열로 바꾼 뒤 기존 문자열에 더해준다.
두가지 방법 중 두번째가 깔끔한 듯 하여 두번째를 선택해서 코드를 마무리했다.
※ 알고리즘 풀이에는 정답은 없기 때문에, 더 효율적인 방법이 존재할 수 있다.
'DS & Algorithm > baekjoon' 카테고리의 다른 글
[백준] 13023번 ABCDE - JavaScript(NodeJS) (0) | 2021.05.27 |
---|---|
[백준] 1932번 정수삼각형 - JavaScript(NodeJS) (0) | 2021.05.17 |
[백준] 1309번 동물원 - JavasScript(NodeJS) (0) | 2021.05.16 |
[백준] 9093번 단어 뒤집기 - JavaScript(NodeJS) (0) | 2021.05.01 |
[백준] 10828번 스택 - JavaScript(NodeJS) (0) | 2021.05.01 |