[JS] 백준 2164 : 카드2 - 큐, 스택, 링크드리스트(push,pop의 비효율)

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

2164번: 카드2

 

 

push나 pop을 사용하면 시간초과가 뜨는 문제다

배열의 연산시간상  맨 앞 요소의 삭제 & 추가하는 연산이 index 수정시간하는 시간이나 다름없기 때문에

연결리스트를 만들어서 사용해야 한다.

 

JS는 연결리스트가 없어서 직접 만들어주면 된다.

 

☝링크드리스트

링크드리스트는 노드로 이루어져 있고 val, ref,add 저장

- find 를 위해서는 시간복잡도 O(n)

- random access를 위해서는 head에서부터 무조건 시작해 각각의 node를 탐색해야 함

 

Node라는 클래스를 생성해서 각 인덱스값에

val : 현재값

next : 다음 값

prev : 이전 값

을 저장한다

 

그리고 LinkedList라는 클래스를 생성해서 

N개의 Node클래스를 저장하는 클래스를 만든다.

이때 LinkedList 클래스는

head : 배열의 맨 처음의 값

tail : 배열의 마지막 값

length : 배열의 길이

를 저장한다.

 

내 제출

const filePath = process.platform === 'linux' ? 'dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString();

const N = Number(input);

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

// LinkedList 클래스 설정
class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    push(val) {
        const newNode = new Node(val);
        
        if (!this.head) {
            this.head = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
        }

        this.tail = newNode;
        this.length++;

        return newNode;
    }

    getHead() { // 첫 노드(head) 가져오기
        return this.head.val;
    }

    removeHead() { // 첫 노드(head)를 연결리스트에서 지우기
        this.head = this.head.next;
        this.head.prev = null;
        this.length--;
    }

    getLength() { // 연결리스트의 길이 알기
        return this.length;
    }
}

const cards = new LinkedList();
for (let i = 1; i <= N; i++) {
    cards.push(i);
}
while (cards.getLength() !== 1) { // 길이가 0 이 아니라면.
    cards.removeHead(); // 맨 앞 노드를 지우고
    cards.push(cards.getHead()); // 맨 앞 노드를 맨뒤로 붙이고
    cards.removeHead(); // 다시 맨 앞 노드를 지우고
}
console.log(cards.getHead());