백준) 28279 - 덱 2 JS

📌 문제 링크

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

---

📌 문제 탐색하기

• 정수를 저장하는 덱을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
• 명령
  • 1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000) 
  • 2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000) 
  • 3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다. 
  • 4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다. 
  • 5: 덱에 들어있는 정수의 개수를 출력한다. 
  • 6: 덱이 비어있으면 1, 아니면 0을 출력한다. 
  • 7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다. 
  • 8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.

시간복잡도

• O(n)

알고리즘 선택

• 덱

---

📌 코드 설계하기

• 문제의 `input`을 개행으로 분리합니다.
• `Deque` 클래스를 만듭니다.
  1. `head`: 덱의 앞쪽 포인터
  2. `tail`: 덱의 뒷쪽 포인터
  3. `items`: 실제 데이터를 저장할 객체
  4. `length`: 덱의 현재 크기
• `Deque` 클래스 메서드를 구현합니다.
  • `pushFront(1 X)`: `head`를 감소시키고 해당 위치에 X 저장
  • `pushBack(2 X)`: `tail` 위치에 X를 저장하고 `tail` 증가
  • `popFront(3)`: `head` 위치의 값을 반환하고 `head` 증가, 비어있으면 -1
  • `popBack(4)`: `tail`을 감소시키고 해당 위치의 값 반환, 비어있으면 -1
  • `size(5)`: 현재 `length` 반환
  • `empty(6)`: `length`가 0이면 1, 아니면 0 반환
  • `front(7)`: `head` 위치의 값 반환, 비어있으면 -1
  • `back(8)`: `tail -1` 위치의 값 반환, 비어있으면 -1
• `Deque`을 생성하고 결과를 저장할 `answer` 배열도 초기화합니다.
•  명령에 맞게 알맞는 메서드를 호출해줍니다.
• 결과를 출력합니다.

---

📌 정답 코드

//https://www.acmicpc.net/problem/28279
export {};

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

interface Items {
  [key: number]: string;
}

class Deque {
  head: number;
  tail: number;
  items: Items;
  length: number;
  constructor() {
    this.head = 0;
    this.tail = 0;
    this.items = {};
    this.length = 0;
  }

  pushFront(value: string) {
    this.head--;
    this.items[this.head] = value;
    this.length++;
  }

  pushBack(value: string) {
    this.items[this.tail] = value;
    this.tail++;
    this.length++;
  }

  popFront() {
    if (this.length === 0) return -1;
    const value = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    this.length--;
    return value;
  }

  popBack() {
    if (this.length === 0) return -1;
    this.tail--;
    const value = this.items[this.tail];
    delete this.items[this.tail];
    this.length--;
    return value;
  }

  size() {
    return this.length;
  }

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

  front() {
    return this.length === 0 ? -1 : this.items[this.head];
  }

  back() {
    return this.length === 0 ? -1 : this.items[this.tail - 1];
  }
}

const deque = new Deque();
const answer = [];

for (const x of input) {
  if (x.startsWith("1")) {
    deque.pushFront(x.split(" ")[1]);
  }
  if (x.startsWith("2")) {
    deque.pushBack(x.split(" ")[1]);
  }
  if (x === "3") {
    answer.push(deque.popFront() || -1);
  }
  if (x === "4") {
    answer.push(deque.popBack() || -1);
  }
  if (x === "5") {
    answer.push(deque.size());
  }
  if (x === "6") {
    answer.push(deque.empty());
  }
  if (x === "7") {
    answer.push(deque.front());
  }
  if (x === "8") {
    answer.push(deque.back());
  }
}
console.log(answer.join("\n"));