프린터

프로그래머스 level2. 스택 / 큐 프린터

프린터 문제링크

문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다.

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

풀이

Queue 를 구현해서 푸는 방법. 값과 인덱스가 필요하므로 자료구조를 묶어줄 필요가 있다. 우선순위에 따라 enqueue와 dequeue 를 진행하면서, dequeue시에 찾아야하는 값 (location) 인지 아닌지 검사한다.

먼저 큐를 구현해보자. 자바스크립트에서 배열의 shift 메서드로도 문제를 풀 수있지만 큐를 구현하면 O(1)로 해결이 가능하다.

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(value) {
    this.queue[this.rear++] = value;
  }

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }

  peek() {
    return this.queue[this.front];
  }

  size() {
    return this.rear - this.front;
  }
}

구현된 큐를 이용해서 문제를 풀어보자.

1. 대기 목록에서 가장 앞에 있는 문서(J) 를 꺼낸다.
2. 나머지 대기 목록에서 중요도가 (J) 보다 높은 문서가 있으면, J를 가장 마지막에 넣는다.
3. 그렇지 않으면 J를 인쇄한다.
4. 1~3 이 반복될 때 location 값으로 주어진 인덱스의 문서가 몇 번째로 인쇄되는지 리턴하라.

function solution(priorities, location) {
  let count = 0;
  const queue = new Queue();

  for (let i = 0; i < priorities.length; i++) {
    queue.enqueue([priorities[i], i]);
  }

  priorities.sort((a, b) => b - a);

  while (queue.size() > 0) {
    const currentValue = queue.peek();

    if (currentValue[0] < priorities[count]) {
      const front = queue.dequeue();
      queue.enqueue(front);
    } else {
      const value = queue.dequeue();
      count++;
      if (location === value[1]) {
        return count;
      }
    }
  }

  return count;
}