[알고리즘] 회전하는 큐 javascript

참 ... 갈수록 내 머리로 풀수 있는 문제인가 싶다.

자료구조 중 큐는 선입선출의 구조를 가지고 있다.

비유하자면 은행 번호표 같은느낌

(1) Enqueue : 큐 맨 뒤에 어떠한 요소를 추가, 마지막으로 온 손님에게 번호표 발부

(2) Dequeue : 큐 맨 앞쪽의 요소를 삭제, 창구에서 서비스를 받은 손님의 번호표를 대기목록에서 삭제

(3) Peek : front에 위치한 데이터를 읽음, 다음 서비스를 받을 손님이 누구인지 확인

(4**) front** : 큐의 맨 앞의 위치(인덱스), 다음 서비스를 받을 손님의 번호

(5**) rear** : 큐의 맨 뒤의 위치(인덱스), 마지막에 온 손님의 번호

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));

양방향 연결리스트를 기반으로 문제를 풀이한다.

enqueue 메소드는 연결리스트의 마지막에 노드를 추가한다.
poll 메소드는 연결리스트의 가장 앞 노드를 삭제한다. (문제의 1번 연산)
rotateToLeft 메소드는 가장 앞 노드를 맨 뒤로 보낸다. (문제의 2번 연산)
rotateToRight 메소드는 가장 마지막 노드를 맨 앞으로 보낸다. (문제의 3번 연산)

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

 

 

https://tesseractjh.tistory.com/45 출저