기초 알고리즘 1/2. 200 - 자료 구조 1
1406번. 에디터

문제

1406번 문제 링크

solution

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

// 왼쪽 스택 - 커서 - 오른쪽 스택
// 위와 같은 구조로 문제 풀이 진행
let lStack = input.shift().split("");

let iter = Number(input.shift());

let rStack = [];

for (let i = 0; i < iter; i++) {
    // 만약 명령어만 있는 input이 들어오면 value는 존재하지 않는다.
    let [cmd, value] = input[i].split(" ");
    
    // 명령어에 따라서 분기 처리
    if(cmd === "L" && lStack.length){
        // lStack에 값이 없다면 가장 앞에 있는 것이므로 이 조건문을 통과. 즉, 명령어 무시.
        // 커서 왼쪽을 의미하는 lStack에서 꺼낸 값을 커서 오른쪽을 의미하는 rStack에 넣는다.
        rStack.push(lStack.pop());   
    } else if(cmd === "D" && rStack.length){
        // rStack에 값이 없다면 가장 뒤에 있는 것이므로 이 조건문을 통과. 즉, 명령어 무시.
        // 커서 오른쪽을 의미하는 rStack에서 꺼낸 값을 커서 왼쪽을 의미하는 lStack에 넣는다.
        lStack.push(rStack.pop());
    } else if(cmd === "B"){
        // 커서 왼쪽을 의미하는 lStack에서 마지막 요소 제거
        lStack.pop();  
    } else if(cmd === "P"){
        // 커서 왼쪽을 의미하는 lStack에 value를 push
        lStack.push(value);
    }
}

// lStack은 맨 앞 ~ 맨 뒤 순서로 되어야지 알맞은 문자열이다.
let answer = lStack.join("");

// rStack은 맨 뒤 ~ 맨 앞 순서로 되어야지 알맞은 문자열이다.
answer += rStack.reverse().join("");

console.log(answer);

하나의 스택을 쓰는 방법이 아니라 두 개의 스택을 사용하는 방법으로 접근했다.
예시를 보면 이해가 빠를 것이다.

입력 데이터
abc
9
L
L
L
L
L
P x
L
B
P y

abc는 입력된 문자열
9는 명령어 횟수
그 뒤로는 명령어이다.

편의상 커서를 #이라고 표현하겠다. 커서는 초기 입력값 문자열의 가장 뒤에 있다.
즉, 현재 문자열의 상태는 abc# 이라고 할 수 있다.

이를 두 개의 스택으로 표현하면 이렇게 된다.
왼쪽 스택  // 커서 // 오른쪽 스택
c // # // 없음
b
a

즉, 커서 #을 기준으로 왼쪽 스택과 오른쪽 스택으로 나눠서 생각하겠다는 것이다.
작동원리를 살펴보자.
만약, abc#def 라는 문자열이 있다면, 왼쪽 스택에는 abc, 오른쪽 스택에는 def가 들어있는 것이다.
여기서 커서가 움직이면 ab#cdef 가 된다.
그렇다면 c는 왼쪽 스택에서 pop 되어서 오른쪽 스택으로 push 될 것이다.
그 결과, 오른쪽 스택에는 

c
d
e
f
이런 형태의 스택이 만들어진다.

왼쪽 스택이
b
a

인 것과 비교하면 나열됐을 때 가장 앞에 있어야하는 문자의 순서가 정반대인 것을 알 수 있다.

우리는 배열을 통해 스택을 구현하기 때문에
lStack = ["a","b"]
커서 #
rStack = ["f","e","d","c"]
이런 식으로 될 것이기 때문이다.
스택은 위에서 넣어서 아래부터 쌓아올리는 구조라서 헷갈릴 수 있는데,
스택을 오른쪽으로 눕혀서 보고 있다고 생각하면 된다.

이제 입력 데이터를 가지고 명령어를 하나씩 실행해보고, 그 결과를 표시해보자.
L : ab#c
lStack = ["a","b"]
커서 #
rStack = ["c"]

L : a#bc
lStack = ["a"]
커서 #
rStack = ["c","b"]

L : #abc
lStack = []
커서 #
rStack = ["c","b","a"]

L : lStack의 길이가 0이므로 명령어 무시
L : lStack의 길이가 0이므로 명령어 무시

P x : x#abc
커서 왼쪽을 의미하는 lStack에 x 문자를 push한다.
lStack = ["x"]
커서 #
rStack = ["c","b","a"]

L : #xabc
lStack = []
커서 #
rStack = ["c","b","a","x"]

B : lStack의 길이가 0이므로 pop을 해도 아무것도 나오지않고, undefined가 리턴된다.

P y : y#xabc
lStack = ["y"]
커서 #
rStack = ["c","b","a","x"]

모든 명령어를 실행했으므로 스택 두 개를 조합해서 하나로 만들어야한다.
lStack은 배열의 순서 그대로 출력하면 된다.
rStack은 스택 구조상 뒤에서부터 출력해야지 맞는 문자열이다.
따라서 rStack.reverse().join("")을 통해 xabc를 만들어준다.

이제 두 문자열을 합친다.
yxabc

끝.

시간 초과

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

// 초기 문자열
// "abcd"가 들어온다면, strArr는 ["a", "b", "c", "d"]가 된다.
let strArr = input.shift().split("");

// 명령어 개수
const iter = input.shift();

// 커서의 초기 위치. 문자열 가장 뒤에 존재한다.
// 문자열이 abc이면 커서의 위치는 인덱스 3이므로, length와 같다고 할 수 있다.
let cursor = strArr.length;

input.forEach((item) => {
    if(item === "L"){
        // cursor를 왼쪽으로 한칸 옮김.
        if(cursor === 0){
            // 만약 cursor가 맨 앞에 있다면, L 명령어는 무시
            return;
        } else {
            // 그게 아니라면 cursor를 왼쪽으로 옮김.
            cursor -= 1;
        }
    } else if(item === "D"){
        // cursor를 오른쪽으로 옮김.
        if(cursor === strArr.length){
            // 만약 cursor가 맨 뒤에 있다면, R 명령어는 무시
            return;
        } else {
            // 그게 아니라면 cursor를 오른쪽으로 옮김.
            cursor += 1;
        }
    } else if(item === "B"){
        // 커서 왼쪽에 있는 문자를 삭제함.
        if(cursor === 0){
            // 만약 cursor가 맨 앞에 있다면, B 명령어는 무시
            return;
        } else {
            // 그게 아니라면 왼쪽에 있는 문자 삭제
            // cursor 왼쪽의 문자를 건드리려면, cursor보다 1 앞에 있는 인덱스에서 삭제해줘야함.
            // splice는 원본 배열이 변경됨. 
            strArr.splice(cursor - 1, 1);
        }
    } else {
        // cursor 왼쪽에 문자를 추가함.
        // cursor 위치에 관계없이 왼쪽에 추가하기만 하면됨.
        // input이 "P x" 이런 식으로 들어오기 때문에 아래와 같은 코드로 추가할 문자열만 분리해줘야함.
        let addNum = item.split(" ")[1];

        // cursor 인덱스에 addNum을 추가한다.
        // splice는 cursor 인덱스 왼쪽에 요소를 추가함.
        strArr.splice(cursor, 0, addNum);
    }
});

console.log(strArr.join(""));

for문으로 했을 때 시간 초과가 걸려서, forEach로 바꿨음에도 시간 초과가 해결되지않았다.
접근법이 틀리지않았다는 것에 만족한다.
여태 for문 정도만 바꾸면 시간 초과를 해결하는 줄 알았더니, 문제 접근법을 다르게 하는 것으로도 시간 초과를 해결할 수 있다는 것을 피부에 와닿게 느낀건 처음인 것 같다..

참고 자료

이 분은 천재가 아닐까..?
참고 자료 1