[백준 / BOJ] 18258번 큐 2 ( Node js / Javascript)

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

18258번: 큐 2

 

 

문제를 처음 읽었을 때는 지난번 풀었던 스택 문제에서 큐로 바뀌기만 했구나 싶어서 크게 어려울 것 없겠다고 생각했다.

그래서 아래와 같이 배열의 shift() 함수를 사용하여 큐의 pop을 구현했었다.

const fs = require("fs");

const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((item) => item.replace("\r", ""));

let queue = [];
let answer = [];

for (let i = 0; i < input.length; i++) {
  let cmd = input[i];
  if (cmd.startsWith("push")) {
    queue.push(Number(cmd.split(" ")[1]));
  }
  if (cmd === "pop") {
    if (queue.length === 0) {
      answer.push("-1");
    } else {
      answer.push(queue.shift());
    }
  }
  if (cmd === "size") {
    answer.push(queue.length);
  }
  if (cmd === "empty") {
    if (queue.length === 0) {
      answer.push("1");
    } else {
      answer.push("0");
    }
  }
  if (cmd === "front") {
    if (queue.length === 0) {
      answer.push("-1");
    } else {
      answer.push(queue[0]);
    }
  }
  if (cmd === "back") {
    if (queue.length === 0) {
      answer.push("-1");
    } else {
      answer.push(queue[queue.length - 1]);
    }
  }
}

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

 

결과는 시간 초과가 났다.

 

 

전혀 예상치도 못하게 시간 초과가 나서 당황스러웠다. 찾아보니 원인은 다음과 같았다.

 

배열의 shift 연산은 위의 그림과 같이 동작하므로 시간 복잡도를 O(n) 으로 갖는다는 것이었다.

그래서 위 문제를 풀기 위해서는 큐를 연결 리스트로 구현해야 한다.

 

 

연결 리스트란

 

이미지 출처 - https://www.freecodecamp.org/korean/news/implementing-a-linked-list-in-javascript/

 

연결 리스트의 한 노드는 다음과 같이 이루어진다.

 

1. 데이터: 원소의 값을 저장하는 부분
2. 포인터(또는 링크): 다음 원소의 위치를 가리키는 부분

 

때문에 노드가 다음 노드의 주소를 가르키고 있기 때문에 연결 리스트라고 부른다.

 

연결리스트로 큐를 구현하면 가장 앞의 데이터를 추출해내도 그 다음의 노드를 헤드로 지정해주기만 하면 되기 때문에

시간복잡도가 O(1)이 된다.

 

 

아래는 연결 리스트 클래스와 Node 클래스다.

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

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

  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  removeFirst() {
    if (!this.head) return null;
    const temp = this.head;
    this.head = this.head.next;
    if (!this.head) this.tail = null;
    this.length--;
    return temp.data;
  }

  get size() {
    return this.length;
  }

  get lastNode() {
    if (!this.tail) return null;
    return this.tail.data;
  }
}

 

다음은 위의 연결 리스트를 사용해 만든 queue다. 문제에서 요구하는 기능들에 맞춰 메서드들을 작성했다.

class Queue {
  constructor() {
    this.linkedList = new LinkedList();
  }

  enqueue(data) {
    this.linkedList.append(data);
  }

  dequeue() {
    return this.linkedList.removeFirst();
  }

  peek() {
    if (!this.linkedList.head) return null;
    return this.linkedList.head.data;
  }

  get length() {
    return this.linkedList.size;
  }

  get lastNode() {
    return this.linkedList.lastNode;
  }
}

 

전체 코드

const fs = require("fs");

const input = fs
  .readFileSync("../input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((item) => item.replace("\r", ""));
input.shift();

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

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

  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  removeFirst() {
    if (!this.head) return null;
    const temp = this.head;
    this.head = this.head.next;
    if (!this.head) this.tail = null;
    this.length--;
    return temp.data;
  }

  get size() {
    return this.length;
  }

  get lastNode() {
    if (!this.tail) return null;
    return this.tail.data;
  }
}

class Queue {
  constructor() {
    this.linkedList = new LinkedList();
  }

  enqueue(data) {
    this.linkedList.append(data);
  }

  dequeue() {
    return this.linkedList.removeFirst();
  }

  peek() {
    if (!this.linkedList.head) return null;
    return this.linkedList.head.data;
  }

  get length() {
    return this.linkedList.size;
  }

  get lastNode() {
    return this.linkedList.lastNode;
  }
}

const queue = new Queue();
let answer = "";

for (let i = 0; i < input.length; i++) {
  if (input[i].startsWith("push")) {
    queue.enqueue(input[i].split(" ")[1]);
  }
  if (input[i] === "pop") {
    if (queue.length === 0) {
      answer += "-1\n";
    } else {
      answer += queue.peek() + "\n";
      queue.dequeue();
    }
  }
  if (input[i] === "size") {
    answer += queue.length + "\n";
  }
  if (input[i] === "empty") {
    if (queue.length === 0) {
      answer += "1\n";
    } else {
      answer += "0\n";
    }
  }
  if (input[i] === "front") {
    if (queue.length === 0) {
      answer += "-1\n";
    } else {
      answer += queue.peek() + "\n";
    }
  }
  if (input[i] === "back") {
    if (queue.length === 0) {
      answer += "-1\n";
    } else {
      answer += queue.lastNode + "\n";
    }
  }
}

console.log(answer);

 

이렇게 배열의 문제점을 연결 리스트를 사용하여 해결했다고 해서 연결 리스트가 배열보다 항상 좋은 것은 아니다.

 

연결 리스트는 배열의 shift연산을 시간 복잡도 O(1) 로 수행할 수 있는 대신,

특정 index의 값을 찾기 위해서는 노드를 하나씩 순차적으로 검사해야 하기 때문에 시간 복잡도 O(N)을 갖게 된다.

 

 

아래는 배열과 연결 리스트의 차이를 시간 복잡도 기준으로 분류한 것이다.

	배열	연결 리스트
접근(탐색)	O(1)	O(N)
삽입(마지막 요소)	O(1)	O(N)
삽입(첫번째 요소)	O(N)	O(1)
삭제(마지막 요소)	O(1)	O(N)
삭제(첫번째 요소)	O(N)	O(1)

 

1. 접근 (Access)
   • 배열: O(1) - 인덱스를 사용하여 직접 접근이 가능하므로 상수 시간에 원하는 위치의 원소를 가져올 수 있다.
   • 연결 리스트: O(n) - 특정 원소에 접근하려면 리스트의 시작부터 해당 원소까지 순회해야 하므로 최악의 경우 전체 노드를 거쳐야 한다.
2. 삽입 (Insertion)
   • 배열:
     • 시작 부분: O(n) - 첫 번째 위치에 원소를 삽입하려면 모든 원소를 한 칸씩 이동시켜야 한다.
     • 중간: O(n) - 중간 위치에 원소를 삽입하려면 해당 위치 이후의 모든 원소를 한 칸씩 이동시켜야 한다.
     • 끝: O(1) - 배열에 남은 공간이 있으면 끝에 원소를 추가하는 것은 상수 시간에 가능하다. 그러나 배열이 꽉 차 있을 경우 배열의 크기를 조정해야 하므로, 이 경우에는 O(n)이 될 수 있다.
   • 연결 리스트:
     • 시작 부분: O(1) - 새로운 노드를 첫 번째 노드로 만들고 기존의 첫 번째 노드를 두 번째 노드로 연결하면 된다.
     • 중간: O(n) - 삽입하려는 위치를 찾기 위해 순회해야 한다.
     • 끝: O(n) - 마지막 노드를 찾기 위해 전체 리스트를 순회해야 한다. (단, 마지막 노드에 대한 포인터를 유지하면 O(1)에 가능)
3. 삭제 (Deletion)
   • 배열:
     • 시작 부분: O(n) - 첫 번째 원소를 삭제하면 모든 원소를 한 칸씩 앞으로 이동시켜야 한다.
     • 중간: O(n) - 중간의 원소를 삭제하면 해당 위치 이후의 모든 원소를 한 칸씩 앞으로 이동시켜야 한다.
     • 끝: O(1) - 마지막 원소를 삭제하는 것은 상수 시간에 가능한다.
   • 연결 리스트:
     • 시작 부분: O(1) - 첫 번째 노드의 링크를 끊고 두 번째 노드를 첫 번째 노드로 만든다.
     • 중간: O(n) - 삭제하려는 위치를 찾기 위해 순회해야 한다.
     • 끝: O(n) - 마지막 노드의 바로 앞 노드를 찾기 위해 전체 리스트를 순회해야 한다.