[백준/연결리스트/JS] 에디터

문제 설명

---

1406번: 에디터

• 소문자만, 600000글자까지
• 커서 위치: 문장 맨 앞, 문장 맨 뒤, 문자 사이
• 맨 처음에 커서는 맨 뒤에 위치
• L: 왼쪽으로 한칸
• D: 오른쪽으로 한칸
• B: 왼쪽에 있는 문자 삭제
• P$: $를 커서 왼쪽에 추가

• 입력값: 문자열, 명령어 개수, 명령어들
• 출력값: 입력값에 모든 명령어 수행한 후의 결과값

 

시간 복잡도

---

arr.splice()

삭제하려는 요소의 위치, 배열 개수에 따라서 시간 복잡도가 달라진다. 

 

삭제하려는 요소가 배열의 맨 끝에 위치할 경우 => O(1)

그 외 => O(n)

 

arr.slice()

자르는 요소의 개수에 따라 시간 복잡도가 달라진다. 

 

자르는 요소를 k개라고 할 때 O(k)의 시간복잡도를 가진다. 

 

틀린 부분

---

let [str, n, ...list] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
list = list.map((el) => el.split(' '));
str = str.split('');

// 처음 커서 위치
let cursor = str.length;

for (let i = 0; i < Number(n); i++) {
​​let el = list[i];
​​// list에 따른 커서 위치 이동
​​if (el[0] === 'P') {
​​​​// str에 값 추가
​​​​// str = [...str.slice(0, cursor), el[1], ...str.slice(cursor)];
​​​​str.splice(cursor, 0, el[1]);
​​​​// 커서 위치 이동
​​​​cursor++;
​​} else if (el[0] === 'L' && cursor > 0) {
​​​​cursor--;
​​} else if (el[0] === 'D' && cursor < str.length) {
​​​​cursor++;
​​} else if (el[0] === 'B' && cursor > 0) {
​​​​// 커서 왼쪽에 있는 문자 제거
​​​​// str = [...str.slice(0, cursor - 1), ...str.slice(cursor)];
​​​​str.splice(cursor - 1, 1);
​​​​cursor--;
​​}
}

console.log(str.join(''));

splie와 slice 모두 시간복잡도가 오래 걸리는 메소드라 테스트 코드 모두 통과하나 시간 초과 오류가 났다. 

 

 

다른 풀이

---

class Node {
​​constructor(value) {
​​​​this.value = value;
​​​​this.next = null;
​​​​this.prev = null;
​​}
}

// 예를 들어 A, B 사이에 C를 넣는다고 가정할 때, 
function insertAfter(node, value) {
​​// 새로 추가할 노드 생성(C)
​​const newNode = new Node(value);
​​// 새로운 노드의 이전 노드는 현재 노드(A)
​​newNode.prev = node;
​​// 새로운 노드의 다음 노드는 현재 노드의 다음 노드(B)
​​newNode.next = node.next;
​​// 중간에 삽입하는 경우
​​if (node.next) {
​​​​// B.prev는 새로운 노드
​​​​node.next.prev = newNode;
​​}
​​// 끝에 삽입하는 경우 새로 추가한 노드를 다음 노드로 변경
​​node.next = newNode;
​​// 새로 추가한 노드 리턴
​​return newNode;
}

// 예를 들어 A, C, B가 연결되어 있다고 가정할 때
function deleteNode(node) {
​​// C.prev는 A
​​const prevNode = node.prev;
​​// C.next는 B
​​const nextNode = node.next;
​​if (prevNode) {
​​​​// A.next는 B
​​​​prevNode.next = nextNode;
​​}
​​if (nextNode) {
​​​​// B.prev는 A
​​​​nextNode.prev = prevNode;
​​}
}

let [str, n, ...list] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
list = list.map((el) => el.split(' '));

// 연결 리스트의 head에 더미 노드 할당
const head = new Node(null);
let cursor = head;

for (let i = 0; i < str.length; i++) {
​​cursor = insertAfter(cursor, str[i]);
}

for (let i = 0; i < n; i++) {
​​let el = list[i];
​​if (el[0] === 'P') {
​​​​cursor = insertAfter(cursor, el[1]);
​​} else if (el[0] === 'L' && cursor.prev) {
​​​​cursor = cursor.prev;
​​} else if (el[0] === 'D' && cursor.next) {
​​​​cursor = cursor.next;
​​} else if (el[0] === 'B' && cursor.prev) {
​​​​const prevNode = cursor.prev;
​​​​deleteNode(cursor);
​​​​cursor = prevNode;
​​}
}

let result = '';
let currentNode = head.next;
while (currentNode) {
​​result += currentNode.value;
​​currentNode = currentNode.next;
}

console.log(result);

코드 짜는 것도 읽는 것도 쉽지 않다.. 연습해야겠다. 

연결 리스트는 class를 사용하여 구현하는 것이 더 쉽다. 

 

 

스택으로 통과한 코드 추가

---

let [str, m, ...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
let stack = [];
let arr = [];
input = input.map((el) => el.split(' '));

for (let i = 0; i < str.length; i++) {
​​stack.push(str[i]);
}

for (let i = 0; i < Number(m); i++) {
​​let el = input[i][0];
​​// $ 값 stack에 추가
​​if (el === 'P') {
​​​​stack.push(input[i][1]);
​​}
​​// 맨 앞이면 무시, stack.pop() 값 arr에 추가
​​else if (el === 'L' && stack.length > 0) {
​​​​let popItem = stack.pop();
​​​​arr.push(popItem);
​​}
​​// 맨 뒤면 무시, arr.pop() 값 stack에 추가
​​else if (el === 'D' && arr.length > 0) {
​​​​let popItem = arr.pop();
​​​​stack.push(popItem);
​​}
​​// 맨 앞이면 무시, stack.pop()
​​else if (el === 'B' && stack.length > 0) {
​​​​stack.pop();
​​}
}

arr.reverse();
console.log([...stack, ...arr].join(''));

 

기억해야 하는 정보

---

• splice와 slice 모두 값비싼 작업이다. 
• 따라서 위와 같은 문제에서는 연결리스트를 사용하여 코드를 작성해야 한다.

 

참고자료

---

• 다른 접근 방식, 블로그

 

---

질문이나 잘못된 점은 댓글로 남겨주세요 :)💖