[백준] 28279번 : 덱 2 with JS

 

링크 : https://www.acmicpc.net/problem/28279

28279번: 덱 2

문제 풀이

 

스택, 큐 공부를 하면서 linked list로 구현하는 것이 재미있어서 풀었지만... 런타임 에러, 시간초과 반복이었다.

런타임 에러와 틀렸습니다 는 말 그대로 코드를 틀린 상황이었고 

시간 초과가 문제였다. 

또한 JS로 풀었던 자료가 별로 없어서 힘들었다..

 

Linked List로 풀기 (실패 - 시간 초과)

const fs = require("fs");
//const input = fs.readFileSync("예제.txt").toString().trim().split("\n");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const n = Number(input[0]);
const arr = input.slice(1);

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

class LinkedList {
  constructor() {
    this.tail = null;
    this.head = null;
    this.length = 0;
  }

  add_first(value) {
    let newNode = new Node(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
  }

  add_last(value) {
    let newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  get_first() {
    if (this.length <= 0) return -1;
    else {
      let value = this.head.value;
      this.head = this.head.next;
      this.length--;
      return value;
    }
  }

  get_last() {
    let tmpNode = this.head;
    let newTail = tmpNode;
    if (!tmpNode) return -1;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    }
    while (tmpNode.next) {
      newTail = tmpNode;
      tmpNode = tmpNode.next;
    }
    this.tail = newTail;
    this.tail.next = null;
    this.length--;

    return tmpNode.value;
  }

  get_length() {
    return this.length;
  }

  isEmpty() {
    return this.length <= 0 ? 1 : 0;
  }

  print_first() {
    return this.length ? this.head.value : -1;
  }

  print_last() {
    return this.length ? this.tail.value : -1;
  }
}

let list = new LinkedList();
let ans = [];
for (let i = 0; i < n; i++) {
  let [cmd, value] = arr[i].split(" ").map(Number);
  switch (cmd) {
    case 1:
      list.add_first(value);
      break;
    case 2:
      list.add_last(value);
      break;
    case 3:
      ans.push(list.get_first());
      break;
    case 4:
      ans.push(list.get_last());
      break;
    case 5:
      ans.push(list.get_length());
      break;
    case 6:
      ans.push(list.isEmpty());
      break;
    case 7:
      ans.push(list.print_first());
      break;
    case 8:
      ans.push(list.print_last());
      break;
  }
}

console.log(ans.join("\n"));

이 코드가 되지 않은 이유는  get_last()에서 데이터를 없앨 때 while문이 있어서 시간 초과가 나온 거 같다.

최대 O(N)까지 실행된 거 같다.

  get_last() {
    let tmpNode = this.head;
    let newTail = tmpNode;
    if (!tmpNode) return -1;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    }
    while (tmpNode.next) {
      newTail = tmpNode;
      tmpNode = tmpNode.next;
    }
    this.tail = newTail;
    this.tail.next = null;
    this.length--;

    return tmpNode.value;
  }

 

---

이 문제를 해결하기 위해.... 이중 연결 리스트를 공부해서 해결해 보자고 생각했다.

(왜냐하면 get_last를 추출할 때 tail의 전 node를 바로 얻을 수 있기 때문이다) 

즉 O(1)의 시간 복잡도를 만들어보자.

 

이중 연결리스트를 공부하려면...

2024.01.25 - [코딩테스트/코테를 위한 알고리즘 & 자료구조 정리] - Doubly Linked List with JS

Doubly Linked List with JS

 

---

최종 코드

const fs = require("fs");
//const input = fs.readFileSync("예제.txt").toString().trim().split("\n");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const n = Number(input[0]);
const arr = input.slice(1);

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null; // New: Previous pointer
  }
}

class DoublyLinkedList {
  constructor() {
    this.tail = null;
    this.head = null;
    this.length = 0;
  }

  add_first(value) {
    let newNode = new Node(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode; // New: Set previous pointer for the old head
      this.head = newNode;
    }
    this.length++;
  }

  add_last(value) {
    let newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  get_first() {
    if (this.length <= 0) return -1;
    else {
      let value = this.head.value;
      this.head = this.head.next;
      if (this.head) {
        this.head.prev = null; // New: Set previous pointer to null for the new head
      } else {
        this.tail = null; // New: If the list becomes empty, update the tail
      }
      this.length--;
      return value;
    }
  }

  get_last() {
    if (this.length <= 0) return -1;
    let value = this.tail.value;
    this.tail = this.tail.prev;
    if (this.tail) {
      this.tail.next = null; // New: Set next pointer to null for the new tail
    } else {
      this.head = null; // New: If the list becomes empty, update the head
    }
    this.length--;
    return value;
  }

  get_length() {
    return this.length;
  }

  isEmpty() {
    return this.length <= 0 ? 1 : 0;
  }

  print_first() {
    return this.length ? this.head.value : -1;
  }

  print_last() {
    return this.length ? this.tail.value : -1;
  }
}

let list = new DoublyLinkedList();
let ans = [];
for (let i = 0; i < n; i++) {
  let [cmd, value] = arr[i].split(" ").map(Number);
  switch (cmd) {
    case 1:
      list.add_first(value);
      break;
    case 2:
      list.add_last(value);
      break;
    case 3:
      ans.push(list.get_first());
      break;
    case 4:
      ans.push(list.get_last());
      break;
    case 5:
      ans.push(list.get_length());
      break;
    case 6:
      ans.push(list.isEmpty());
      break;
    case 7:
      ans.push(list.print_first());
      break;
    case 8:
      ans.push(list.print_last());
      break;
  }
}

console.log(ans.join("\n"));