[백준/연결리스트/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 모두 값비싼 작업이다. 
• 따라서 위와 같은 문제에서는 연결리스트를 사용하여 코드를 작성해야 한다.

 

참고자료

---

• 다른 접근 방식, 블로그

 

---

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