백준 1966번 프린터 큐 - node.js

해당 포스팅은 백준 1966번 프린터 큐 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.

문제

1. 각 원소의 우선순위가 있는 큐이다.

2. 현재 Queue의 가장 앞에 있는 문서의 중요도를 확인한다.

   • 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 있다면 이 문서를 Queue의 가장 뒤에 재배치한다.
   • 이 문서가 가장 중요도가 높으면 바로 인쇄한다.

3. 예시:
   Queue에 4개의 문서(A, B, C, D)가 있고, 중요도가 2, 1, 4, 3이라고 가정하자. C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄한다.

   • A보다 C가 더 우선순위가 높으므로 뒤로 재배치한다. (B, C, D, A)
   • B보다 C가 더 우선순위가 높으므로 뒤로 재배치한다. (C, D, A, B)
   • C가 가장 중요도가 높으므로 C를 인쇄한다. (D, A, B)
   • D가 가장 중요도가 높으므로 D를 인새한다. (A, B)
   • A가 가장 중요도가 높으므로 A를 인쇄한다. (B)
   • B가 가장 중요도가 높으므로 B를 인쇄한다. ()

4. 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 출력하자.
   예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

1. [첫째 줄] : 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.
   이후는 테스트케이스들이 주어진다.

2. [테스트케이스] :

   • 첫째 줄: 1) 문서의 개수 N(1 ≤ N ≤ 100)과, 2) 몇 번째로 인쇄되었는지 궁금한 문서의 현재 Queue에서의 인덱스 M(0 ≤ M < N)
   • 둘째 줄: N개 문서의 중요도가 차례대로 주어진다.
     중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

풀이

문서들의 인덱스를 기억하고 있어야 하므로, Queue에 각 문서들을 [문서 인덱스, 문서 우선순위]로 저장한다. 그리고 loop를 돌리면서, 현재 el가 가장 높은 우선순위인지에 따라 출력 / 재배치를 진행한다.

예제를 통해 구체적인 로직을 설명하겠다.

예제

설명을 위해 아래 예제를 풀이해보겠다.

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

• 첫 번째 줄은 테스트 케이스의 개수이므로 testCnt로 저장하자.
• 출력 횟수를 저장할 변수 cnt를 선언한다.
• 테스트 케이스는 2줄이므로 testCnt * 2만큼 loop를 돌린다.
• loop에서 두 번째 테스트 케이스를 판별한다고 가정해보자.
  
  

1. 두 번째 테스트케이스는 4~5번째 줄이다.

   • [4번째 줄] :
     두 번째 테스트케이스의 첫 번째 줄로, 해당 테케의 문서의 개수 N, 궁금한 문서의 현재 인덱스 M가 주어진다.
     (해당 NM은 input[i].split(" ")를 통해 구할 수 있다.)
     → NM = [4, 2]

   • [5번째 줄]
     : 두 번째 테스트케이스의 두 번째 줄로, N개 문서의 중요도 priority가 주어진다.
     (해당 priority는 input[i+1].split(" ")를 통해 구할 수 있다.)
     → priority = [1,2,3,4]
     
     

2. Queue에 [문서의 인덱스, 문서의 우선순위]를 집어넣는다.
   : Queue = [[0, 1], [1, 2], [2, 3], [3, 4]]
   
   

3. 중첩 while문을 돌린다.

   • outer while문은 가장 높은 우선순위를 계산한 후 maxPriority에 저장한다.
   • inner while문은 현재 front가 maxPriority와 동일한지 아닌지에 따라 출력 / 재배치를 한다.
     • 현재 큐의 front가 maxPriority와 동일하면 1) 출력횟수 cnt를 1 늘리고 2) dequeue한다.
       이 때 front가 M과 동일할 시(찾고자 한 문서) cnt를 출력하고 outer를 빠져나온다. M과 동일하지 않을 시 inner를 탈출한 후 maxPriority를 계산 후 동일한 과정을 반복한다.
     • 현재 큐의 front가 maxPriority와 동일하지 않다면 front를 큐의 맨 뒤로 재배치한다.

전체 코드

const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
class Queue {
    constructor() {
        this.arr = [];
    }
    enqueue(item) {
        this.arr.push(item);
    }
    dequeue() {
        return this.arr.shift();
    }
    front() {
        return this.arr[0];
    }
}
const testCnt = input[0];
for (let i = 1; i < testCnt * 2; i += 2) {
    const q = new Queue();
    let cnt = 0;

    const NM = input[i].split(" ");
    const N = Number(NM[0]); // 문서 개수
    const M = Number(NM[1]); // 찾고자 하는 문서의 인덱스

    const priority = input[i + 1].split(" "); // 문서의 우선순위

    // [문서 인덱스, 문서 우선순위]
    for (let i = 0; i < N; i++) {
        q.enqueue([i, Number(priority[i])]);
    }

    outer: while (true) {
        let maxPriority = 0;
        // maxPrority 구하기
        for (let i = 0; i < q.arr.length; i++) {
            let currPrority = q.arr[i][1];
            if (currPrority > maxPriority) {
                maxPriority = currPrority;
            }
        }
        inner: while (true) {
            const currItem = q.front();
            const currIdx = currItem[0];
            const currPrority = currItem[1];
            // front가 가장 높은 우선순위일 시
            if (maxPriority === currPrority) {
                cnt++;
                q.dequeue();
                // 정답일 시
                if (currIdx === M) {
                    console.log(cnt);
                    break outer;
                }
                // 그 다음 원소로 넘어가기
                break inner;
            } else {
                q.dequeue();
                q.enqueue(currItem);
            }
        }
    }
}```