문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 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 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력

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

예제 입력

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

예제 출력

1
2
5

내가 했던 풀이 방법

1. queue를 생성하고, 테스트 케이스에 첫 번째 줄을 공백으로 분할하여 N과 M에 저장하고, 두 번째 줄을 공백으로 분할하여 documents 배열에 저장해준다. (line 변수를 이용하여 해당 줄을 사용할 때마다 line을 1씩 증가시켜준다.)
2. documnets을 순회하면서 queue에 해당 documents 값을 넣어준다. 이때, M번째 documents의 값은 10을 더한 값으로 넣어준다. (M번째 문서가 인쇄되는 것을 알아내기 위해 10을 더해주었다. 중요도는 1~9범위만을 가질 수 있으므로, 10을 더해주면 다른 값과 다른 점을 확실하게 알 수 있고, 10으로 나누었을 때의 나머지가 원래 값과 같기 때문에 기존 값을 기억할 수도 있다.)
3. documnets를 내림차순으로 정렬해준다. (중요도가 클수록 먼저 인쇄되므로, 정렬한 값과 같은 문서는 삭제해주면 된다.)
4. index를 0으로 초기화해주고, M번째 문서가 인쇄될 때까지 반복해준다. queue.current()는 다음으로 삭제될 값을 반환해준다. 즉 front가 가리키고 있는 값이다. 해당 값이 documents[index] 값과 같을 경우, 삭제해주고 index를 1 증가시켜준다. 만약 queue.current()를 10으로 나눈 나머지가 documents[index]와 같을 경우에도 삭제하고 index를 1 증가해주고, 현재 while문을 탈출한다. documents[index]와 같지 않을 경우, queue.dequeue한 값을 enqueue해준다. (맨 뒤로 보내준다.)
5. 탈출한 뒤에 index를 출력한다. (index는 0부터 시작하기 때문에 주의해야 한다. 해당 문서가 삭제될 때에도 index를 1 증가시킨 뒤, 탈출했기 때문에 추가로 +1을 해줄 필요가 없다.)

코드

const fs = require('fs');
let [cases, ...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');
cases = Number(cases);
let N = 0;
let M = 0;
let documents = [];

class Queue {
  constructor() {
    (this.storage = {}), (this.front = 0), (this.rear = 0);
  }

  size() {
    if (this.storage[this.rear] === undefined) return 0;
    else return this.rear - this.front + 1;
  }

  enqueue(value) {
    if (this.size() === 0) this.storage[0] = value;
    else {
      this.rear += 1;
      this.storage[this.rear] = value;
    }
  }

  dequeue() {
    let value = this.storage[this.front];
    delete this.storage[this.front];
    if (this.front === this.rear) {
      this.front = 0;
      this.rear = 0;
    } else this.front += 1;
    return value;
  }

  current() {
    return this.storage[this.front];
  }
}

let line = 0;
for (let i = 0; i < cases; i++) {
  let queue = new Queue();
  N = Number(input[line].trim().split(' ')[0]);
  M = Number(input[line++].trim().split(' ')[1]);
  documents = input[line++].trim().split(' ').map(Number);

  for (let j = 0; j < documents.length; j++) {
    if (j === M) queue.enqueue(documents[j] + 10);
    else queue.enqueue(documents[j]);
  }

  documents.sort((a, b) => b - a);
  let index = 0;
  while (true) {
    if (documents.length === index) break;
    if (queue.current() === documents[index]) {
      queue.dequeue();
      index++;
    } else if (queue.current() % 10 === documents[index]) {
      queue.dequeue();
      index++;
      break;
    } else {
      queue.enqueue(queue.dequeue());
    }
  }
  console.log(index);
}

회고

큐를 이용해서 쉽게 삭제를 하는 것까지 구현하긴 했으나... 삭제되는 문서가 어떤 것인지를 알아내기가 너무 어려웠다. 중요도가 모두 다르면 괜찮지만, 마지막 예제처럼 중요도 1이 5개나 있을 경우, 어느 것이 먼저 삭제될지는 모르기 때문이다. 처음에는 해당 문서의 key값을 저장해둘까 했는데.. 계속 맨 뒤로 가면서 key값이 자주 바뀌기 때문에 좋지 않은 방법 같아서 고민을 많이했다. 다행히 10을 더해주자는 좋은 방법이 떠올랐다. (오랜만에 알고리즘 잘 짠 것 같음)
우선순위 큐를 이용하면 쉽다는데 오늘은 큐만 공부했기 때문에 우선순위 큐는 며칠 뒤에 공부해서 다른 문제에서 구현해보도록 하겠다.