[BOJ]28279 - 덱2(JS)

덱 구조를 활용하는 문제이다. 

처음 풀이

let fs = require("fs");
let input = fs.readFileSync('예제.txt').toString().trim().split("\n");
let N = Number(input[0])
input.shift();
let ans = [];
for(let x of input){
    if(x[0] == 1){
        let [a,b] = x.split(" ");
        ans.unshift(Number(b))
    }
    if(x[0] == 2){
        let [a,b] = x.split(" ");
        ans.push(Number(b))
    }
    if(x[0] == 3){
        if(ans.length !== 0){
            console.log(ans.shift())
            
        }else{
            console.log(-1)
        }
    }
    if(x[0] == 4){
        if(ans.length !== 0){
            console.log(ans.pop())
        }else{
            console.log(-1)
        }
    }
    if(x[0] == 5){
        console.log(ans.length)
    }
    if(x[0] == 6 ){
        if(ans.length !== 0){
            console.log(0)
        }else{
            console.log(1)
        }
    }
    if(x[0] == 7){
        if(ans.length !== 0){
            console.log(ans[0])
        }else{
            console.log(-1)
        }
    }
    if(x[0] == 8){
        if(ans.length !== 0){
            console.log(ans[ans.length-1])
        }else{
            console.log(-1)
        }
    }
}

 

처음엔 shift 와 unshift를 이용해서 넣었는데 시간초과로 인해 실패했다 연산이 오래걸리는듯 하다.

 

https://arnopark.tistory.com/838

[백준/nodeJS] 28279. 덱 2

이 분의 풀이를 참고했다 스택 , 큐 , 덱등의 개념을 일절 몰랐던 나는 너무 도움이 되었다.

 

우선 덱 이란?

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다.

 

스택과 큐를 합친 구조이다. 왜 이것을 사용해야 하는가? 

shift 의 시간 복잡도는 O(N) 이다. 덱을 사용하면 O(1) 을 유지한 채로 풀이가 가능하다.

const fs = require("fs");
const [N, ...input] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const n = 1000000;
let output = "";

const deque = new Array(n);
let size = 0;
let front = -1;
let rear = -1;

const addFirst = (e) => {
  if (size === 0) {
    front = 0;
    rear = 0;
  } else {
    if (front === 0) {
      front = n - 1;
    } else {
      front--;
    }
  }

  deque[front] = e;
  size++;
};

const addLast = (e) => {
  if (size === 0) {
    front = 0;
    rear = 0;
  } else {
    if (rear === n - 1) {
      rear = 0;
    } else {
      rear++;
    }
  }

  deque[rear] = e;
  size++;
};

const removeFirst = () => {
  output += deque[front] + "\n";
  size--;
  if (front === n - 1) {
    front = 0;
  } else {
    front++;
  }
};

const removeLast = () => {
  output += deque[rear] + "\n";
  size--;

  if (rear === 0) {
    rear = n - 1;
  } else {
    rear--;
  }
};

input.forEach((e) => {
  const [exe, num] = e.split(" ").map(Number);

  if (exe === 1) {
    addFirst(num);
  }

  if (exe === 2) {
    addLast(num);
  }

  if (exe === 3) {
    size === 0 ? (output += "-1\n") : removeFirst();
  }

  if (exe === 4) {
    size === 0 ? (output += "-1\n") : removeLast();
  }

  if (exe === 5) {
    output += size + "\n";
  }

  if (exe === 6) {
    size === 0 ? (output += "1\n") : (output += "0\n");
  }

  if (exe === 7) {
    size === 0 ? (output += "-1\n") : (output += deque[front] + "\n");
  }

  if (exe === 8) {
    size === 0 ? (output += "-1\n") : (output += deque[rear] + "\n");
  }
});

console.log(output);