[백준] 28279, 덱2

문제 풀이

덱 자료구조는 앞에서도 뒤에서도 데이터를 삽입, 추출이 가능한 자료구조라고 할 수 있다.
자바스크립트에서 배열을 사용해서 쉽게 구현할 수 있지만 삽입, 추출에 시간복잡도가 O(n)으로 입력값이 많아진다면 시간 초과가 발생할 수 있다.

나의 경우에는 연결리스트를 통해서 덱을 직접 구현하여 문제를 해결했다.
연결리스트를 통해서 덱을 구현했다면 문제를 푸는 것은 어렵지 않을 것이라고 생각한다.

덱

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

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

  unshift(value) {
    const node = new Node(value);
    if (this.length === 0) {
      this.head = node;
      this.tail = node;
    } else {
      const head = this.head;
      this.head = node;
      this.head.next = head;
      head.prev = this.head;
    }
    this.length++;
  }

  push(value) {
    const node = new Node(value);
    if (this.length === 0) {
      this.tail = node;
      this.head = node;
    } else {
      const tail = this.tail;
      this.tail = node;
      this.tail.prev = tail;
      tail.next = this.tail;
    }
    this.length++;
  }

  shift() {
    const head = this.head;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = head.next;
      this.head.prev = null;
    }
    this.length--;
    return head;
  }

  pop() {
    const tail = this.tail;
    if (this.length === 1) {
      this.tail = null;
      this.head = null;
    } else {
      this.tail = tail.prev;
      this.tail.next = null;
    }
    this.length--;
    return tail;
  }
}

제출 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [n, ...input] = fs.readFileSync(filePath).toString().trim().split("\n");

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

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

  unshift(value) {
    const node = new Node(value);
    if (this.length === 0) {
      this.head = node;
      this.tail = node;
    } else {
      const head = this.head;
      this.head = node;
      this.head.next = head;
      head.prev = this.head;
    }
    this.length++;
  }

  push(value) {
    const node = new Node(value);
    if (this.length === 0) {
      this.tail = node;
      this.head = node;
    } else {
      const tail = this.tail;
      this.tail = node;
      this.tail.prev = tail;
      tail.next = this.tail;
    }
    this.length++;
  }

  shift() {
    const head = this.head;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = head.next;
      this.head.prev = null;
    }
    this.length--;
    return head;
  }

  pop() {
    const tail = this.tail;
    if (this.length === 1) {
      this.tail = null;
      this.head = null;
    } else {
      this.tail = tail.prev;
      this.tail.next = null;
    }
    this.length--;
    return tail;
  }
}

const deque = new Deque();
const arr = input.map((v) => v.split(" "));
const answer = [];

arr.forEach((v) => {
  const [commnad, X] = v;
  switch (commnad) {
    case "1":
      deque.unshift(X);
      break;

    case "2":
      deque.push(X);
      break;

    case "3":
      if (deque.length > 0) {
        const head = deque.shift();
        answer.push(head.value);
      } else {
        answer.push(-1);
      }
      break;

    case "4":
      if (deque.length > 0) {
        const tail = deque.pop();
        answer.push(tail.value);
      } else {
        answer.push(-1);
      }
      break;

    case "5":
      answer.push(deque.length);
      break;

    case "6":
      answer.push(deque.length === 0 ? 1 : 0);
      break;

    case "7":
      if (deque.length > 0) {
        answer.push(deque.head.value);
      } else {
        answer.push(-1);
      }
      break;

    case "8":
      if (deque.length > 0) {
        answer.push(deque.tail.value);
      } else {
        answer.push(-1);
      }
      break;

    default:
      break;
  }
});
console.log(answer.join("\n"));

출처
https://www.acmicpc.net/problem/28279