[백준/JS] 1966번 : 프린터 큐

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

[ 문제 설명 ]

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

 첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다.

 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다. 

 

아래는 예제 입력1에 대한 설명이다.

3 // 테스트케이스의 수 
// 아래부터 테이스케이스는 두줄씩 이루어짐 

1 0 // 문서의 개수는 1개이며 ,  몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 0번째에 놓여있다.
5 // 1개 문서의 중요도는 5이다 

4 2 // 문서의 개수는 4개이며 ,  몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 2번째에 놓여있다.
1 2 3 4 // 4개 문서의 중요도는 1,2,3,4

6 0 // 문서의 개수는 6개이며 ,  몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 0번째에 놓여있다.
1 1 9 1 1 1 // 6개 문서의 중요도는 1,1,9,1,1,1

 

이에 따른 예제 출력1에 대한 설명은 아래와 같다. 각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

1 // 1개의 문서중 0번째 놓여있는 문서는 5밖에 없으므로 1번째로 출력된다. 
2 // 4개의 문서중 2번째 놓여있는 문서는 3이므로 중요도(4->3)에 따라 2번째로 출력된다.
5 // 6개의 문서중 0번째 놓여있는 문서는 1이므로 중요도(9->1->1->1->1)에 따라 5번째로 출력된다.

 

---

[ 문제 풀이 과정 ]

 

1. 큐 클래스를 만든다.

2. 테스트 케이스 두번째줄에 중요도와 인덱스를 배열 형태로 큐에 집어넣는다. 

3. testArr이란 배열을 만들어 두번째줄의 중요도를 집어넣은 후 오름차순 정렬해준다. 

4. 2와 3을 비교해 다르면 큐의 가장 뒤에 배치하고 같으면 답으로 출력한다. (아래 주석으로 자세히 설명) 

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n").map((e) => e.replace("\r", ""));

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.back = 0;
  }
  push(x) {
    this.storage[this.back] = x;
    this.back += 1;
  }
  popleft() {
    const temp = this.storage[this.front];
    this.front += 1;
    return temp;
  }
}

const answer = [];
const T = input[0]; //테스트케이스 개수
let i = 0;

for (let j = 0; j < T; j++) {
  const [N, M] = input[i + 1].split(" "); // 테스트 케이스 첫번째 줄 
  const doc = input[i + 2].split(" "); // 테스트 케이스 두번째 줄
  const queue = new Queue();

  let count = 1; // 문서가 몇번째로 인쇄되었는지 (답으로 출력될 부분)
  const testArr = [];
  let n = 0; // 테스트 케이스 두번째줄 중요도 별 인덱스
  for (x of doc) {
    queue.push([x, n++]); // {[1,0],[1,1]..}
    testArr.push(x); // [1,1,9,1,1,1]
  }
  testArr.sort((a, b) => a - b); // [1,1,1,1,1,9]

  while (testArr.length > 0) {
    let isBreak = false;
    // 중요도 높은순
    const ta = testArr.pop(); 
    while (true) {
      // 가장 앞에 있는 문서부터 중요도 확인
      const qp = queue.popleft(); // [1,0]      
      //오름차순으로 정렬된 testArr의 첫번째 요소와 
      // 테스트 케이스 두번째 줄의 첫번째 요소 중요도가 같지 않으면 
      if (ta != qp[0]) { 
        queue.push(qp); // 큐의 가장 뒤에 재배치
      } else { 
        // 테스트 케이스 두번째 줄에서 각 중요도의 인덱스와 
        // 테스트 케이스 첫번째 줄에서 몇번째로 놓여있는지 궁금한 문서의 위치(M)이 같다면
        if (qp[1] == M) { 
          answer.push(count); // 그 문서가 몇번째로 출력되는 지 answer에 추가
          isBreak = true;
        }
        count += 1;
        break;
      }
    }
    if (isBreak == true) {
      break;
    }
  }
  i += 2; 
}
console.log(answer.join("\n"));