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

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

2164번: 카드2

 

• 사용언어 : node.js
• 알고리즘 : 자료구조, 큐
• Solved.ac Tier : Silver IV

 

node.js 코드

1. 문제 정리

간단하게 사진 한장으로 정리되는 문제이다. 항상 맨 위에 있는 카드는 없애고, 삭제되고 난 뒤 젤 위에 있는 카드를 맨 아래로 보내면 되는 문제이다. 위에 카드는 사라지고 아래 카드는 들어오는 구조는 바로 큐이다. 선입 선출 방식을 이용하여 먼저 코드를 짜보았다. 

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'ans.txt';
let input = require('fs').readFileSync(filePath).toString().trim().split("\n");

class Queue{
    constructor(arr){
        this.arr = arr;
    }
    s_push(num){
        this.arr.push(num);
    }
    s_pop(){
        let data = this.arr.shift();
        if(!data) return -1
        return data;
    }
    s_empty(){
        if(this.arr.length > 0){
            return 0;
        }
        else{
            return 1;
        }
    }
    s_size(){
        return this.arr.length;
    }
}


const arr = [...new Array(parseInt(input))].map((_, i) => i + 1);
let queue = new Queue(arr);


for(;;){
    if(queue.s_size() == 1) break;
    queue.s_pop(); //젤 위 카드 삭제
    queue.s_push(queue.s_pop()) //젤 위 카드 아래로 내리기
}

console.log(queue.s_pop());

결과는 제대로 출력 되었지만 시간 초과가 났다. 아마 pop 하는 과정에서의 shift() 연산이 O(1)만에 되는 것이 아니라, O(n^2) 이상이기 때문에 생기는 결과인 것 같았다. 

따라서 다른 방식을 사용해야 했다. 더 빠르게 조작 할 수 있는 Linked List를 이용하여 문제를 해결 해 보았다.

https://www.geeksforgeeks.org/introduction-and-insertion-in-a-doubly-linked-list/

간단하게 doubley linked list를 나타낸 사진이다. 모든 노드에 prev와 next가 존재하고 각각 주소를 가르키거나 null 값을 가지고 있도록 만들어져 있다.

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

따라서 노드의 생성자 함수에 value, next, prev 값을 넣은 링크드리스트를 만들었다. 

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

    push(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.length++;
        return newNode;
    }

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

    removeHead() { 
        this.head = this.head.next;
        this.head.prev = null;
        this.length--;
    }

    getSize() { 
        return this.length;
    }
}

링크드 리스트 클래스 안에는 push, getHead, removeHead, getSize 함수들을 만들었다. Queue 역할을 할 수 있는 LinkedList 클래스를 만들어 주었다. 

이제 시간 초과 났던 방법과 똑같이 작성 해 주면 문제가 해결된다. shift의 시간 복잡도 O(n^2)보다 빠른 removeHead의 시간 복잡도 O(1) 덕분에 시간 초과 나지 않고 해결 할 수 있는 문제이다. 

2. 완성 코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'ans.txt';
let input = require('fs').readFileSync(filePath).toString().trim().split("\n");

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

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

    push(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.length++;
        return newNode;
    }

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

    removeHead() { 
        this.head = this.head.next;
        this.head.prev = null;
        this.length--;
    }

    getSize() { 
        return this.length;
    }
}

const list = new LinkedList();

for(let i = 1; i <= input; i++) list.push(i);

for(;;){
    if(list.getSize() <= 1) break;
    list.removeHead();
    list.push(list.getHead());
    list.removeHead()
}

console.log(list.getHead());