[백준] 자바스크립트(node.js) 1996번 '프린터 큐' 문제 풀이

백준 자바스크립트(node.js) 1996번 프린터 큐 문제 풀이

📖 들어가며

자바스크립트(nodejs)로 백준 1966번 문제인 큐 자료구조를 사용하여 '프린터 큐' 문제를 풀이해보겠다.

❓ 문제 

문제 설명

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다.
하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
  1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
  2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의       가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

• 첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.
• 테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력

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

예제 입력 1

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

예제 출력 1

1
2
5

💡 풀이

문제에서 순서대로 처리한다는 문장을 보고 즉,  FIFO '큐' 자료구조를 사용하는 문제인 것을 알 수 있었다.

첫 번째로는 3개의 테스트 케이스를 입력받기 위해서 입력 값을 받고 반복문 안에 솔루션 코드를 작성하면서 테스트 케이스의 개수만큼 처리할 수 있도록 해주었다.

const fs = require('fs');
const file = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs.readFileSync(file).toString().trim().split('\n');

let [n, ...arr] = input;
arr = arr.map((item) => item.split(' ').map(Number));
let answer = '';

for (let i = 0; i < arr.length; i += 2) {
  let count = 0;
  const priorities = arr[i + 1];
  let location = arr[i][1];
  ...
}

console.log(answer.trim());

이후에, while문으로 알고자하는 프린터의 순서를 알 때까지 반복문을 실행하도록 했다.

while문 안에서는 제일 중요도가 높은 프린터를 max 변수에 담아두고,

첫 번째로 들어가 있는 프린터를 뽑아서 해당 프린터가 중요도가 제일 높은 프린터인지 비교를 하는데, 해당 프린터가 중요도가 제일 높은 프린터라면 count를 올리면서 몇 번째로 뽑혔는지 결과를 저장하고, 그 안에서도 중요도가 높고 같은 프린터가 여러 개 있을 수 있으니 찾고자 했던 프린터의 위치가 0번 인덱스 즉, 현재 뽑은 프린터가 맞다면 answer에 count를 추가하고 while문을 빠져나갈 수 있도록 break를 걸어주었다.

 

하지만 현재 뽑은 프린터가 제일 중요도가 높은 프린터가 아니라면 해당 프린터의 순서를 맨 뒤로 보낼 수 있게 끔 push를 해주었다.

 

해당 코드들을 지나 왔으면 찾고자 하는 프린터의 위치가 앞으로 밀리므로 위치를 변경해 주어야 한다.

해당 위치가 0번째 인덱스였다면 마지막 인덱스로 변경해주고, 아니면 -1을 함으로써 위치를 정확히 알 수 있도록 했다.

 

모든 테스트 케이스를 처리하고 나면 마지막에 결과를 출력한다.

풀이 코드

const fs = require('fs');
const file = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs.readFileSync(file).toString().trim().split('\n');

let [n, ...arr] = input;
arr = arr.map((item) => item.split(' ').map(Number));
let answer = '';

for (let i = 0; i < arr.length; i += 2) {
  let count = 0;
  const priorities = arr[i + 1];
  let location = arr[i][1];

  while (true) {
    const max = Math.max(...priorities);
    const number = priorities.shift();
    if (number === max) {
      count++;
      if (location === 0) {
        answer += count + '\n';
        break;
      }
    } else {
      priorities.push(number);
    }

    if (location === 0) {
      location = priorities.length - 1;
    } else {
      location--;
    }
  }
}

console.log(answer.trim());

✔ 채점

제출 결과