[JavaScript] 백준 코딩테스트 10866. 실버 4 : 덱

📌  문제

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

📌  입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

📌  출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

📌  예제 입출력

---

📌  풀이

알아야 하는 것

• 덱(Double Ended Queue): 양쪽 끝에서 삽입/삭제가 가능한 자료구조
  • 데이터 추가 O(1) / 데이터 삭제 O(1) / 맨 앞과 맨 뒤의 데이터 확인 O(1)
  • 배열로 덱을 구현할 때 unshift()나 shift()처럼 앞쪽 데이터를 추가하고 삭제하는 경우, 최대 O(N)까지 시간 복잡도가 증가할 수 있다. 
  • 덱은 배열 외에도 링크드 리스트로 구현할 수 있다. (⭐️)

구할 것

• 덱을 직접 가공하는 게 아니라 덱과 관련된 명령을 수행할 때 그 값을 answer라는 다른 배열에 넣어준다.
• 명령이 총 8가지로 모두 if문을 쓸 수 있지만 처음으로 switch case문을 써 풀어보았다.
  • 첫 줄을 제외한 input값들을 한 줄씩 순회하되 split(" ")으로 나눠주었다.
  • 해서 명령과 명령 시 덱에 넣거나 뺄 수를 order, num으로 구조 분해 할당한다.
  • case에 맞는 order가 들어온다면 그 부분을 수행하게 한다.
    • break를 하지 않으면 다음 케이스로 넘어가게 된다. 계속 해서 모든 케이스들이 실행됨에 따라 출력 초과가 날 수 있으니 반드시 break를 작성해 해당하는 명령에 맞는 액션 후 멈춰준다.

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

const numOfOrder = Number(input.shift());
let deque = [];
let answer = [];

for (let i = 0; i < numOfOrder; i++) {
  let [order, num] = input[i].split(" ");

  switch (order) {
    case "push_front":
      deque.unshift(Number(num));
      break;

    case "push_back":
      deque.push(Number(num));
      break;

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

    case "pop_back":
      answer.push(deque.length === 0 ? -1 : deque.pop() || -1);
      break;

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

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

    case "front":
      answer.push(deque.length === 0 ? -1 : deque[0]);
      break;

    case "back":
      answer.push(deque.length === 0 ? -1 : deque[deque.length - 1]);
      break;
  }
}

console.log(answer.join('\n'));