문제

: 중요도가 높은 문서를 먼저 인쇄하는 프린터가 있다.

이 프린터의 작동 과정

1. 인쇄 대기목록 가장 앞에 있는 문서(J)를 대기목록에서 꺼낸다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면, J를 대기목록의 가장 마지막에 넣는다.
3. 그렇지 않으면 J를 인쇄한다.

• 현재 대기 목록에는 1 ~ 100개의 문서가 있다.
• 인쇄 작업의 중요도는 1 ~ 9로 표현하며, 숫자가 클수록 중요하다.
• location은 0 ~ [총 개수 - 1] 의 값을 가지며, 대기 목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현한다.

입력값

• priorities : 현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열
• location : 현재 대기목록에서 내가 인쇄하려는 문서의 위치(index)

출력값

내가 인쇄하려는 문서가 몇 번째로 인쇄되는지 리턴한다.

입출력 예

priorities	location	return
[2, 1, 3, 2]	2	1
[1, 1, 9, 1, 1, 1]	0	5

---

이 문제는 Queue 문제이다.
먼저 연결 리스트를 이용해 Queue를 만들어야 한다.

연결 리스트로 Queue 만들기

// Node 클래스
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// Queue 클래스
class Queue {
  constructor() {
    this.head = null; // 생성자에서는 head와 tail을 null로 지정한다.
    this.tail = null;
    this.size = 0;
  }
  
  // 요소를 추가하기 위한 enqueue 함수
  enqueue(newValue) { 
    const newNode = new Node(newValue); // 값을 받아 새로운 노드를 생성한다.
    if(this.head === null) { // head가 비어있는 경우, head와 tail에 생성한 노드를 넣어준다.
      this.head = this.tail = newNode;
    } else { // head가 비어있지 않은 경우,
      this.tail.next = newNode; // 꼬리 부분에 next에 생성한 노드를 넣어준다.
      this.tail = newNode; // 새로 추가된 노드가 꼬리가 되도록 설정해준다.
    }
    this.size++;
  }
  
  // 요소를 빼기 위한 dequeue 함수
  dequeue() {
    const value = this.head.value; // head의 값을 별도의 변수에 담아두고,
    this.head = this.head.next; // 리스트에서 head를 제거한다.
    this.size--;
    return value; // 앞서 담아둔 head의 값을 반환한다.
  }
  
  // head의 값을 그대로 리턴하는 peek 함수
  peek() {
    return this.head.value;
  }
}

---

이제 솔루션 함수에서 Queue를 이용해 답을 도출할 수 있다.

의사 코드

function solution(priorities, location) {
  Queue 생성자를 이용해 큐를 만든다.
  반복문 (priorities 배열을 순회하며) {
    큐에 [요소, index]를 넣어준다.
  }
  
  priorities 배열을 내림차순으로 정렬해준다. (숫자가 높을 수록 중요도가 크므로)
  이때 priorities 배열을 따로 정렬해주는 이유는 빠른 탐색과 효율성을 위해서이다.
  
  찾고자하는 문서가 몇 번째로 출력되는지 카운팅하기 위한 변수 counter를 만든다.
  반복문 (큐의 길이가 0이 될 때까지 순회하며) {
    현재값 = 큐의 맨 앞의 값
    만약 (현재값이 priorites 배열에서 가장 우선순위가 높은 값보다 작다면) {
      큐에서 dequeue해주고, 다시 enqueue해준다.
    } 만약 현재값이 더 크다면, {
      큐에서 dequeue 해주고, 해당 값을 변수 printValue에 저장한다.
      문서 하나가 출력되었으므로 counter를 1 증가시킨다.
      만약 (찾고자하는 문서의 위치가 printValue의 index와 같다면) {
        counter를 리턴한다.
      }
    }
  }
  counter를 리턴한다. (이 리턴문은 실행되지 않을 것이지만 작성해준다.)
}

---

풀이

function solution(priorities, location) { // priorities = [2, 1, 3, 2], locaiton = 2
  const queue = new Queue();
  for (let i = 0; i < priorities.length; i++) {
    queue.enqueue([priorities[i], i]); // queue = [[2, 0], [1 , 1], [3, 2], [2, 3]]
  }
  
  priorities.sort((a, b) => b - a);// priorities = [ 3, 2, 2, 1]
  
  let count = 0;
  while (queue.size > 0) {
    const currentValue = queue.peek();
    if (currentValue[0] < priorities[count]) { // 2 < 3 → 1 < 3 → 3 = 3
      queue.enqueue(queue.dequeue())
      // queue = [[2, 0], [1, 1], [3, 2], [2, 3]]
      // queue = [[1, 1], [3, 2], [2, 3], [2, 0]]
      // queue = [[3, 2], [2, 3], [2, 0], [1, 1]]
    } else {
      const value = queue.dequeue(); // queue = [[2, 3], [2, 0], [1, 1]], value = [3, 2]
      count++;
      if (location === value[1]) { // 2 === 2
        return count; // 3
      }
    }
  }
  return count;
}