[JS][백준]1966_프린터 큐

문제 번호

1966번: 프린터 큐

 

 

 

알고리즘 분류

• 구현
• 자료 구조
• 시뮬레이션
• 큐

 

문제 풀이

 C++에는 STL을 활용해서 Queue와 Dequeue등을 손쉽게 사용할 수 있다.

근데? JS에는 그런거없다. 그래서 직접 만들어서 사용해야한다.

 

우선 queue안에 들어갈 내용물인 node를 만들어준다.

class node {
  constructor(no, pri) { // 문서 번호와 우선순위.
    this.no = no;
    this.pri = pri;
    this.next = null;
  }
}

문제에서 문서별로 우선순위가 다르게 주어진다. 그리고 같은 우선수위를 갖는경우도 있다고 하였으니 각 문서마다 0,1,~~ 순서로 번호를 매기고 우선순위를 기록해두어야 한다. 

 이렇게 주어지면 0번의 우선순위는 1, 1번의 우선순위는 2 이런식으로 짝지어서 기록한다.

이제 저 내용들로 이루어진 Queue를 만들어야한다. Queue자체를 모르거나 Queue를 만드는것에 대해서는 다른블로그에도 더 좋은 설명들이 많이있다. 나는 최대한 내가 다시 사용할 수 있도록 짯다. 

class queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  push(no, pri) {
    let qnode = new node(no, pri);
    if (this.size === 0) {
      this.head = qnode;
    } else {
      this.tail.next = qnode;
    }
    this.tail = qnode;
    this.size++;
  }
  pop() {
    if (this.size === 0) {
      return null;
    } else {
      let tmp = this.head;
      this.head = this.head.next;
      this.size--;
      return [tmp.no,tmp.pri]
    }
  }
}

 

이제 문제에서 주어진대로 구현만 하면된다. 그런데 현재 가장 앞(head)에 있는 문서의 우선순위보다 더 높은 우선순위를 갖은 문서가 Queue에 존재한다면 head의 문서를 출력할 수 없다. 이를 쉽게 확인하기위해서 우선순위만 들어있는 배열을 사용하기로 하였다. 문서를 출력할때마다 현재 Queue에 남아있는 문서들의 우선순위 값중에 가장 높은 우선순위의 값을 max라는 변수에 저장하기로 했다.

  printer.sort((a,b)=>{ // 우선순위가 가장 높은 문서부터 출력해야한다.
    return a - b;
  })
  let max = printer[printer.length - 1];

 

 문서를 바로 출력할 수 있는 경우는 예외로 생각하여 따로 처리하였다. 그외에는 cnt변수를 사용하여 몇번째에 출력되는지 계산한다.

  if (!cnt) cnt = 1;
  return cnt;

 

전체코드

const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
class node {
  constructor(no, pri) { // 문서 번호와 우선순위.
    this.no = no;
    this.pri = pri;
    this.next = null;
  }
}
class queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  push(no, pri) {
    let qnode = new node(no, pri);
    if (this.size === 0) {
      this.head = qnode;
      //this.tail = qnode;
      //this.size++;
    } else {
      this.tail.next = qnode;
      //this.tail = qnode;
      //this.size++;
    }
    this.tail = qnode;
    this.size++;
  }
  pop() {
    if (this.size === 0) {
      return null;
    } else {
      let tmp = this.head;
      this.head = this.head.next;
      this.size--;
      return [tmp.no,tmp.pri]
    }
  }
}
function sol(i) {
  let cnt = 0;

  let [N, K] = input[i].split(' ').map(Number);
  let printer = input[i + 1].split(' ').map(Number);
  
  
  let q = new queue();
  for (let i = 0; i < N; i++) {
    q.push(i, printer[i]);
  }
  printer.sort((a,b)=>{ // 우선순위가 가장 높은 문서부터 출력해야한다.
    return a - b;
  })
  let max = printer[printer.length - 1];
  
  let no, pri;
  while (1) {
    if (q.head.pri >= max) {
      [no,pri] = q.pop();
      cnt++;
      if(no === K)  // 원하는 자료 프린트시 죵료
        break;
      printer.pop();
      max = printer[printer.length - 1];      
    } else {
      let [no, pri] = q.pop();
      q.push(no,pri);
    }
  }

  if (!cnt) cnt = 1;
  return cnt;
}
function main() {
  let answer = '';

  let TC = +input[0];
  for (let i = 1; i <= TC * 2; i += 2) {
    answer += sol(i) + '\n';
  }

  console.log(answer.trim());
}
main();

 

특이사항

 C++과 달리 자료구조를 직접 구현해야해서 많이 고생했다. 하지만 막상 한번 해보고나니까 별거 아니라는걸 깨달았다.

고생했던 부분은 pop 하는 과정에서 문서의 번호(no)와 문서의 우선순위(pri) 2개를 모두 받아와야해서 node class와 return 값을 어떻게 해야할지 고민했었다. 알고리즘 문제를 풀면서 this를 써본적이 없고 class 도 따로 선언해서 풀어본적이 없었는데 좋은 공부가 된거같다.