[백준] 18258번 : 큐 2 with JS

 

링크 : https://www.acmicpc.net/problem/18258

18258번: 큐 2

문제 풀이

 

링크드리스트를 공부하고 큐 문제를 해결하려고 했다.

결국 문제를 해결했지만 정말 문제가 더티하다....

이 문제는 아래의 순서로 공부를 하면 풀 수 있었다.  

1. linked list를 아는가?

2024.01.23 - [코딩테스트/코테를 위한 알고리즘 & 자료구조 정리] - Singly Linked Lists with JS

Singly Linked Lists with JS

2. stack & queue 개념을 아는가? 

https://devuna.tistory.com/22

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시

3. 속도 차이 : 큐 구현 vs 배열 객체 사용 

https://velog.io/@grap3fruit/JS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84-%ED%81%90Queue-%EA%B5%AC%ED%98%84%ED%96%88%EC%9D%84%EB%95%8C-vs-Array-%EB%A9%94%EC%84%9C%EB%93%9Cshift-splice-%EC%82%AC%EC%9A%A9%ED%96%88%EC%9D%84%EB%95%8C-%EC%86%8D%EB%8F%84-%EB%B9%84%EA%B5%90

JS 알고리즘 구현: 큐(Queue) 구현 vs Array 메서드(shift, splice) 사용했을때 속도 비교

 

이렇게만 하면 풀 수 있을줄 알았지만

마지막에 배열에 push 가 아닌

문자열에 저장 후에 join을 해서 데이터 크기를 줄이는 작업까지 해야 성공이다.

 

const fs = require("fs");
const [n, ...arr] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

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

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

  enqueue(value) {
    let newNode = new Node(value);
    this.length++;
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }
  pop() {
    if (!this.head) return -1;
    let pop = this.head;
    this.head = pop.next;
    this.length--;
    return pop.value;
  }
  front() {
    if (!this.head) return -1;
    return this.head.value;
  }
  back() {
    if (!this.head) return -1;
    return this.tail.value;
  }
  empty() {
    if (!this.head) return 1;
    else return 0;
  }
  size() {
    return this.length;
  }
}

let queue = new Queue();
let answer = "";
for (let i = 0; i < n; i++) {
  let [cmd, value] = arr[i].split(" ");
  switch (cmd) {
    case "push":
      queue.enqueue(Number(value));
      break;
    case "pop":
      answer += queue.pop() + " ";
      break;
    case "size":
      answer += queue.size() + " ";
      break;
    case "empty":
      answer += queue.empty() + " ";
      break;
    case "front":
      answer += queue.front() + " ";
      break;
    case "back":
      answer += queue.back() + " ";
      break;
    default:
      break;
  }
}
console.log(answer.split(" ").join("\n"));