📌 문제 설명

표 편집 문제 보기

📌 문제 접근

선택, 삭제, 복구

이런 문구가 보이면 연결리스트를 떠올린다. 특히 이번엔 n이 1000000이기 때문에 삭제할 때 O(n), 다시 복구할 때 O(n)이기 때문에 무조건 시간 초과를 유도하는 문제라고 생각했다.

연결 리스트 구현하기

이번에는 result가 전부 확인 하는 문제라서 node에 data를 추가하였다. 원래는 메모리 주소만 입력하면 됨.

이후에, 초기화를 해주고, 제일 중요한 주소가 null일 때만 신경 써주었다.

AI의 팁

new 키워드 100만개 생성 시 가비지 컬렉터에 부하가 있을 수 도 있다고 지적하였다. 따라서, Int32Array를 사용하는 것도 좋은 선택이라고 한다.

const prev = new Int32Array(n);
const next = new Int32Array(n);

for (let i = 0; i < n; i++) {
  prev[i] = i - 1;
  next[i] = i + 1;
}
next[n - 1] = -1;

📌 내가 작성한 코드

class Node {
  constructor(data, prev = null, next = null) {
    this.data = data;
    this.prev = prev;
    this.next = next;
  }
}

class LinkedList {
  constructor(n, k) {
    this.prev = null;
    this.next = null;
    this.trash = [];

    let last_node = new Node(0, this.prev);
    this.prev = last_node;
    this.start = last_node;

    for (let i = 1; i < n; i++) {
      const node = new Node(i, this.prev);
      last_node.next = node;
      last_node = node;
      this.prev = last_node;
      if (i === k) this.start = last_node;
    }
  }
  u(num) {
    for (let i = 0; i < num; i++) {
      this.start = this.start.prev;
    }
  }
  d(num) {
    for (let i = 0; i < num; i++) {
      this.start = this.start.next;
    }
  }
  c() {
    this.trash.push(this.start);

    const prevNode = this.start.prev;
    const nextNode = this.start.next;

    if (prevNode !== null) prevNode.next = nextNode;
    if (nextNode !== null) nextNode.prev = prevNode;

    this.start = nextNode !== null ? nextNode : prevNode;
  }
  z() {
    const node = this.trash.pop();
    if (node.prev !== null) node.prev.next = node;
    if (node.next !== null) node.next.prev = node;
  }
}

function solution(n, k, cmd) {
  const list = new LinkedList(n, k);
  for (const command of cmd) {
    const [action, num] = command.split(" ");
    if (action === "U") list.u(Number(num));
    else if (action === "D") list.d(Number(num));
    else if (action === "C") list.c();
    else if (action === "Z") list.z();
  }
  const answer = Array(n).fill("O");
  for (const node of list.trash) {
    answer[node.data] = "X";
  }
  return answer.join("");
}

📌 시간 복잡도

• U, D 명령은 이동한 칸 수만큼 순회하고, 나머지 명령은 O(1)이므로 전체 시간 복잡도는 모든 이동 횟수의 합을 M이라 할 때 O(M + C)

📌 참고 링크

• 이중 연결 리스트