[JavaScript] 백준 1021 회전하는 큐 (JS)

회전하는 큐

📚 문제 설명

---

• 회전이 가능한 큐가 있다.
• 큐는 왼쪽 혹은 오른쪽으로 회전할 수 있다.
• 1부터 N 까지 있는 자연수가 큐에 들어있다.
• 큐의 첫번째 원소에서 값을 가져올 때, 원하는 숫자들을 뽑으려면 몇번의 회전이 필요한가

예시

N : 10
월하는 숫자: 1,2,3

1, 2, 3, 4, 5, 6, 7, 8, 9, 10
^ 
2, 3, 4, 5, 6, 7, 8, 9, 10
^
3, 4, 5, 6, 7, 8, 9, 10
^
각각 첫번째를 제거하면 되기 때문에 필요한 회전수 0

👨🏻‍💻 풀이 과정

---

이 문제의 회전하는 큐는 이전에 구현해봤던 덱(DEQUE)으로 구현이 가능하다.
그럼 회전하는 큐는 덱(DEQUE)으로 구현한다고 생각하고 전체적 로직을 생각해보자

• 덱(DEQUE)에 N 까지의 자연수를 push
• Target(원하는 숫자)까지 거리를 계산
  • 왼쪽부터의 거리 leftDis 를 this.start 부터 다음 노드로 가며 계산
  • 오른쪽의 거리 rightDis 를 this.end 부터 이전 노드로 가며 계산
• leftDis 와 rightDis 의 크기 비교후 왼쪽 회전 혹은 오른쪽 회전 선택
• 회전을 진행할 때마다 answer + 1

Solution함수 코드

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    const [N, M] = input.shift().split(' ').map(Number);
    input = input[0].split(' ').map(Number);

    class NODE {
		//생략
    }

    class DEQUE {
		//생략
    }

    const solution = (n, INPUT) => {
        const Deque = new DEQUE();
      	// 회전 수 계산 변수
        let answer = 0;
      	// Deque에 1~N 까지의 자연수 Push
        for (let i = 1; i <= n; i++) {
            Deque.PushBack(i);
        }
      	// 원하는 숫자 찾기
        for (let i = 0; i < INPUT.length; i++) {
            const Target = INPUT[i];
          	// 첫번째 값이 원하는 값이 아닐 때
            if (Deque.getStart() !== Target) {
                let leftDis = 0;
                let rightDis = 0;
              	// cur를 왼쪽 첫번째 값으로 초기화
              	// 왼쪽 첫번째부터 목표 숫자까지 거리 계산
                let cur = Deque.getFirstNode();
                while (cur.node !== Target) {
                    cur = cur.next;
                    leftDis++;
                }
              	// cur를 오른쪽 끝으로 초기화
              	// 오른쪽 끝부터 목표 숫자까지 거리 계산
                cur = Deque.getLastNode();
                while (cur.node !== Target) {
                    cur = cur.prev;
                    rightDis++;
                }
				// 거리에 따라 왼쪽 회전 혹은 오른쪽 회전
                if (leftDis <= rightDis) {
                    while (Deque.getStart() !== Target) {
                        Deque.RotateLeft();
                        answer++;
                    }
                    if (Deque.getStart() === Target) {
                        Deque.PopFront();
                    }
                } else {
                    while (Deque.getStart() !== Target) {
                        Deque.RotateRight();
                        answer++;
                    }
                }
            }
          	// 만약 첫번째 값이 목표 숫자라면 Pop
            if (Deque.getStart() === Target) {
                Deque.PopFront();
            }
        }
        console.log(answer);
    };
    solution(N, input);

💡 덱(DEQUE) 구현

---

덱(DEQUE)은 연결 리스트를 이용하여 구현을 할 예정이고
각각은 Node 로 연결할 것이며, Node는 다음과 같이 구성할 예정이다.

변수	설명
node	현재 값
next	다음 Node
prev	이전 Node

그럼 각각의 기능에 대해 풀어서 생각을 해보자

PushFront
이미지를 this.start 앞에 PushElement(넣어줄 값) 을 붙여주고 this.start를 PushElement로 바꿔준다고 생각해보자.

• PushElement 라는 Node를 생성
• this.start.prev 에 PushElement를 연결
• PushElement.next 에 this.start를 연결
• this.start를 PushElement로 변경

    PushFront(element) {
        const PushElement = new NODE(element);
        PushElement.node = element;
        if (this.length === 0) {
            this.start = PushElement;
            this.end = PushElement;
        } else {
            this.start.prev = PushElement;
            PushElement.next = this.start;
            this.start = PushElement;
        }
      
      // 덱의 길이를 직접 카운팅해야함
        this.length++;
    }

PopFront
전체 덱(Deque)의 길이에 따라 다르게 구현해야 한다.

• 길이가 0이면 불가능하기에 바로 return
• this.start 값을 PopElement 에 저장
• this.start 값을 this.start.next로 변경
• 길이가 1이면 덱에 값이 없어지기에 null 로 변경
• 길이가 2이상이면 this.start 값의 prev 즉 this.start.prev 값을 null 로 변경

    PopFront() {
        if (this.length === 0) return false;
        const PopElement = this.start;
        this.start = this.start.next;
        if (this.length === 1) {
            this.start = null;
        } else {
            this.start.prev = null;
        }
      	// 덱의 길이 갱신
        this.length--;
        return PopElement.node;
    }

이제 여기까지 왔으면 구현은 다 끝났다. 회전의 경우 아래와 같이 이미 구현한 기능으로 구현할 수 있고
덱(Deque)의 끝에서 Push, Pop하는 기능은 위의 Push, Pop을 변형하면 구현이 가능하다.

명령	덱(DEQUE)에 적용시
왼쪽으로 회전	Pop.Front 한 후 값을 Push.End
오른쪽으로 회전	Pop.End 한 후 값을 Push.Front
값을 꺼냄	Pop.Front

덱(DEQUE) 구현 코드

    class NODE {
        constructor(item) {
            this.node = item;
            this.prev = null;
            this.next = null;
        }
    }

    class DEQUE {
        constructor() {
            this.start = null;
            this.end = null;
            this.length = 0;
        }

        PushFront(element) {
            const PushElement = new NODE(element);
            PushElement.node = element;
            if (this.length === 0) {
                this.start = PushElement;
                this.end = PushElement;
            } else {
                this.start.prev = PushElement;
                PushElement.next = this.start;
                this.start = PushElement;
            }
            this.length++;
        }

        PushBack(element) {
            const PushElement = new NODE(element);
            if (this.length === 0) {
                this.start = PushElement;
                this.end = PushElement;
            } else {
                this.end.next = PushElement;
                PushElement.prev = this.end;
                this.end = PushElement;
            }
            this.length++;
        }

        PopFront() {
            if (this.length === 0) return false;
            const PopElement = this.start;
            this.start = this.start.next;
            if (this.length === 1) {
                this.start = null;
            } else {
                this.start.prev = null;
            }
            this.length--;
            return PopElement.node;
        }

        PopEnd() {
            if (this.length === 0) return false;
            const PopElement = this.end;
            this.end = this.end.prev;
            if (this.length === 1) {
                this.end = null;
            } else {
                this.end.next = null;
            }
            this.length--;
            return PopElement.node;
        }

        getStart() {
            return this.start.node;
        }

        getFirstNode() {
            return this.start;
        }

        getLastNode() {
            return this.end;
        }

        RotateLeft() {
            this.PushBack(this.PopFront());
        }

        RotateRight() {
            this.PushFront(this.PopEnd());
        }
    }

전체 코드

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    const [N, M] = input.shift().split(' ').map(Number);
    input = input[0].split(' ').map(Number);

    class NODE {
        constructor(item) {
            this.node = item;
            this.prev = null;
            this.next = null;
        }
    }

    class DEQUE {
        constructor() {
            this.start = null;
            this.end = null;
            this.length = 0;
        }

        PushFront(element) {
            const PushElement = new NODE(element);
            PushElement.node = element;
            if (this.length === 0) {
                this.start = PushElement;
                this.end = PushElement;
            } else {
                this.start.prev = PushElement;
                PushElement.next = this.start;
                this.start = PushElement;
            }
            this.length++;
        }

        PushBack(element) {
            const PushElement = new NODE(element);
            if (this.length === 0) {
                this.start = PushElement;
                this.end = PushElement;
            } else {
                this.end.next = PushElement;
                PushElement.prev = this.end;
                this.end = PushElement;
            }
            this.length++;
        }

        PopFront() {
            if (this.length === 0) return false;
            const PopElement = this.start;
            this.start = this.start.next;
            if (this.length === 1) {
                this.start = null;
            } else {
                this.start.prev = null;
            }
            this.length--;
            return PopElement.node;
        }

        PopEnd() {
            if (this.length === 0) return false;
            const PopElement = this.end;
            this.end = this.end.prev;
            if (this.length === 1) {
                this.end = null;
            } else {
                this.end.next = null;
            }
            this.length--;
            return PopElement.node;
        }

        getStart() {
            return this.start.node;
        }

        getFirstNode() {
            return this.start;
        }

        getLastNode() {
            return this.end;
        }

        RotateLeft() {
            this.PushBack(this.PopFront());
        }

        RotateRight() {
            this.PushFront(this.PopEnd());
        }
    }

    const solution = (n, INPUT) => {
        const Deque = new DEQUE();
        let answer = 0;
        for (let i = 1; i <= n; i++) {
            Deque.PushBack(i);
        }
        for (let i = 0; i < INPUT.length; i++) {
            const Target = INPUT[i];
            if (Deque.getStart() !== Target) {
                let leftDis = 0;
                let rightDis = 0;
                let cur = Deque.getFirstNode();
                while (cur.node !== Target) {
                    cur = cur.next;
                    leftDis++;
                }
                cur = Deque.getLastNode();
                while (cur.node !== Target) {
                    cur = cur.prev;
                    rightDis++;
                }

                if (leftDis <= rightDis) {
                    while (Deque.getStart() !== Target) {
                        Deque.RotateLeft();
                        answer++;
                    }
                } else {
                    while (Deque.getStart() !== Target) {
                        Deque.RotateRight();
                        answer++;
                    }
                }
            }
            if (Deque.getStart() === Target) {
                Deque.PopFront();
            }
        }
        console.log(answer);
    };
    solution(N, input);

🧐 후기

---

저번에 덱(Deque)를 쓰는 문제에서 포인터를 이용하여 풀었기 때문에 연결 리스트를 이용해 덱(Deque)을 구현하지 못했는데 이번 문제를 통해 구현할 수 있었다. 연결 리스트를 직접 구현하려다 보니 Push Pop 기능을 구현하며, 연결 관계를 생각하는 게 너무 복잡해서 힘들었다. 연결 리스트를 이용하여 덱(Deque)을 구현하는 코드는 더욱더 곱씹고 생각해야겠다.