백준) 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"));