[백준 1021] 회전하는 큐 with Node.js

문제 링크

www.acmicpc.net/problem/1021

1021번: 회전하는 큐

풀이

const [n, m, ...arr] = require("fs").readFileSync("/dev/stdin").toString().trim().split(/\s/).map(v => +v);
let count = 0;

function Node(value) {
    this.value = value;
    this.prevNode = null;
    this.nextNode = null;
}

function DoublyLinkedList() {
    this.front = null;
    this.rear = null;
    this.length = 0;

    this.enqueue = value => {
        let curNode = new Node(value);
        if (this.front) {
            curNode.prevNode = this.rear;
            curNode.nextNode = this.front;
            this.rear.nextNode = curNode;
            this.front.prevNode = curNode;
            this.rear = curNode;
        } else {
            this.front = curNode;
            this.rear = curNode;
            curNode.prevNode = curNode;
            curNode.nextNode = curNode;
        }
        this.length++;
    };

    this.poll = () => {
        if (this.length === 1) {
            this.front = null;
            this.rear = null;
        } else {
            let secondNode = this.front.nextNode
            secondNode.prevNode = this.rear;
            this.rear.nextNode = secondNode;
            this.front = secondNode;
            this.length--;
        }
    }

    this.rotateToLeft = (n=1) => {
        while (n > 0) {
            if (this.length > 1) {
                this.rear = this.front;
                this.front = this.front.nextNode;
            }
            n--;
        }
    }

    this.rotateToRight = (n=1) => {
        while (n > 0) {
            if (this.length > 1) {
                this.front = this.rear;
                this.rear = this.rear.prevNode;
            }
            n--;
        }
    }

    this.extract = value => {
        if (this.length <= 1) {
            return 0;
        } else {
            let curNode = this.front;
            let leftCount = 0;
            let rightCount = 0;
            while (curNode.value !== value) {
                curNode = curNode.nextNode;
                leftCount++;
            }
            curNode = this.front;
            while (curNode.value !== value) {
                curNode = curNode.prevNode;
                rightCount++;
            }
            
            if (leftCount < rightCount) {
                this.rotateToLeft(leftCount);
                this.poll();
                return leftCount;
            } else {
                this.rotateToRight(rightCount);
                this.poll();
                return rightCount;
            }
        }
    }
}

dll = new DoublyLinkedList();
for (let i=1; i<=n; i++) dll.enqueue(i);
console.log(arr.reduce((acc, v) => acc + dll.extract(v), 0));

양방향 연결리스트(Doubly Linked List)를 기반으로 문제를 푸는데 필요한 메서드만을 가진 적절한 자료구조를 생성자 함수로 구현하였다.

 

enqueue 메소드는 연결리스트의 마지막에 노드를 추가한다.

poll 메소드는 연결리스트의 가장 앞 노드를 삭제한다. (문제의 1번 연산)

rotateToLeft 메소드는 가장 앞 노드를 맨 뒤로 보낸다. (문제의 2번 연산)

rotateToRight 메소드는 가장 마지막 노드를 맨 앞으로 보낸다. (문제의 3번 연산)

 

extract 메소드는 인수로 받은 value값을 가지는 노드를 찾기 위해 왼쪽과 오른쪽 모두 탐색을 한 후, 가장 짧은 탐색이 가능한 방향으로 rotateToLeft/rotateToRight 한 후에 해당 value를 가진 노드를 poll하여 삭제한다. 그리고 연산이 몇 번 이루어졌는지 그 횟수를 반환한다.

 

 

연결리스트를 생성하고 1부터 n까지의 value를 가지는 Node n개를 추가한다. 그 다음에 지민이가 뽑아내려고 하는 수들(arr)을 차례차례 뽑으면서 연산 횟수를 누적하여 출력하였다.

 

 

코드를 짜면서 DoublyLinkedList가 잘 작동하는지 아래의 메서드를 만들어서 확인해보았다.

this.print = () => {
    let curNode = this.front;
    const nodes = [curNode.value];
    while (curNode.nextNode !== this.front) {
        curNode = curNode.nextNode;
        nodes.push(curNode.value);
    }
    console.log(nodes.join(" -> "));
};

dll = new DoublyLinkedList();
for (let i=1; i<=10; i++) dll.enqueue(i);
dll.print(); // 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
dll.poll();
dll.print(); // 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
dll.rotateToLeft();
dll.print(); // 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 2
dll.rotateToRight();
dll.print(); // 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10