[백준 / 2164 / node.js] 카드 2 javascript

처음에는 그냥 class로 queue를 구현해서 동작시키려고 했다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const n = parseInt(input.shift())

class Queue {
    constructor(num){
        this.arr = [];
    }
    enqueue(num){
        this.arr.push(num);
    }
    drop(){
        this.arr.shift();
    }
    move(){
        this.enqueue(this.arr.shift())
    }
    length(){
        return this.arr.length;
    }
    ans(){
        return this.arr.shift();
    }
}

const card = new Queue;

for(let i=1; i<=n; i++){
    card.enqueue(i);
}

while(card.length()!==1){
    card.drop()
    card.move();

}

console.log(card.ans())

근데 이렇게하면 기본적으로 배열을 사용하기 때문에 push와 shift 를 사용하는 과정에서 시간 복잡도가 너무 커짐.

왜냐면 배열의 경우 제일 앞의 값을 지운경우 나머지 뒤의 값들을 다 한 칸씩 당겨야함.

삽입삭제가 빈번한 경우 LinkedList를 사용해야 한다. 

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const n = parseInt(input.shift())

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

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

    add(value){
        const newNode = new Node(value);

        if(!this.head)
            this.head = newNode;
        else{
            this.tail.next = newNode
            newNode.prev = this.tail
        }

        this.tail = newNode
        this._size++;

        return newNode;
    }

    getHead(){
        return this.head.value;
    }

    removeHead(){
        this.head = this.head.next;
        this.head.prev = null;
        this._size--;
    }
    getSize(){
        return this._size;
    }
}

const node = new LinkedList();

for(let i=1; i<=n;i++){
    node.add(i);
}
while(node.getSize() !==1){
    node.removeHead();
    node.add(node.getHead());
    node.removeHead();
}

console.log(node.getHead());

 

아우 이제야 통과하네..