Tesseractjh
한 걸음씩
Tesseractjh
전체 방문자
오늘
어제
  • 전체 (293)
    • IT (30)
      • JavaScript (7)
      • TypeScript (5)
      • React (5)
      • Next.js (3)
      • MongoDB (2)
      • Webpack (2)
      • HTML & CSS (1)
      • Git (0)
      • AWS (1)
      • 기타 (4)
    • 연습장 (259)
      • 백준(BOJ) 문제풀이 (185)
      • 프로그래머스 문제풀이 (61)
      • LeetCode 문제풀이 (2)
      • HackerRank 문제풀이 (7)
      • 낙서장 (3)
      • 기타 (1)
    • 프로젝트 (3)
      • 지뢰피하기 (1)
      • 키릴-라틴 문자 변환기 (1)
      • Flex & Grid (1)
    • 멋쟁이사자처럼 프론트엔드 스쿨 1기 (1)
      • 일기 & 회고록 (1)

인기 글

티스토리

hELLO · Designed By 정상우.
Tesseractjh

한 걸음씩

연습장/백준(BOJ) 문제풀이

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

2021. 4. 14. 01:46

문제 링크

www.acmicpc.net/problem/1021

 

1021번: 회전하는 큐

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가

www.acmicpc.net

풀이

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
저작자표시 비영리 (새창열림)

'연습장 > 백준(BOJ) 문제풀이' 카테고리의 다른 글

[백준 1003] 피보나치 함수 with Python  (0) 2021.04.14
[백준 9095] 1, 2, 3 더하기 with Python  (0) 2021.04.14
[백준 10816] 숫자 카드 2 with Node.js  (0) 2021.04.13
[백준 2217] 로프 with Node.js  (0) 2021.04.13
[백준 1436] 영화감독 숌 with Node.js  (0) 2021.04.11
    '연습장/백준(BOJ) 문제풀이' 카테고리의 다른 글
    • [백준 1003] 피보나치 함수 with Python
    • [백준 9095] 1, 2, 3 더하기 with Python
    • [백준 10816] 숫자 카드 2 with Node.js
    • [백준 2217] 로프 with Node.js
    Tesseractjh
    Tesseractjh
    바닐라 자바스크립트를 좋아하는 개발자입니다

    티스토리툴바