[220일차]boj 2164 nodejs(연결리스트 응용문제)

백준 2164번 카드 2

문제링크

Code

const readline = require("readline");
 
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
const input = [];
 
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;
    }
}
 
function getLastCard(n) {
    const cards = new LinkedList();
 
    for (let i = 1; i <= n; i++) {
        cards.add(i);
    }
    while (cards.getSize() !== 1) {
        cards.removeHead();
        cards.add(cards.getHead());
        cards.removeHead();
    }
 
    return cards.getHead();
}
 
rl.on("line", function (line) {
    input.push(line);
}).on("close", function () {
    const N = +input[0];
 
    const card = getLastCard(N);
    console.log(card);
 
    process.exit();
});

description

배열의 push pop을 이용하면 시간초과가 뜬다.
배열의 연산시간상 맨앞요소에 삭제추가하는데 다른요소들의 인덱스를 수정하기위한 시간이 많이들기 때문
그래서 비교적 시간량이 적은 연결리스트를 만들어서 활용한다.
javascript는 내장 연결리스트 자료구조가 없으니 직접만들자
전체 기능을 다 만들필요는 없고 가장 앞부분의 요소를 제거하는 메소드와,
가장 앞부분을 불러오는 메소드만 구현하자.