[PS] 프로그래머스 프린터 구현 문제

문제 출처:  https://programmers.co.kr/learn/courses/30/lessons/42587 

코딩테스트 연습 - 프린터

 

지나치게 많은 과업이 쌓여갈 때, 우리는 흔히 대기열을 만들듯이 목록의 끝에 과업들을 추가하고 먼저 들어온 과업부터 순서대로 처리한다. 먼저 들어온 것을 먼저 처리하고, 나중에 들어온 것을 나중에 처리하는것. 우리에게 익숙한 이 First In First Out이라는 개념을 가진 자료구조가 바로 큐(Queue)다. 오늘은 이 큐 자료구조를 활용한 문제를 풀어보고, 그 과정을 정리해보고자 한다. 

 

문제에서는 작업순서가 큐로 구현된 프린터를 소재로 준다. 먼저 요청된 문서가 먼저 출력되고, 나중에 요청된 문서가 나중에 출력된다. 그러나 이 절차에는 중간에 들어온 중요한 문서가 나중에 인쇄될 수 있다는 문제가 있다. 따라서 중요도라는 값이 추가되어, 기본적으로는 큐의 형태로 실행되되 중요도라는 값을 고려하여 실행될 프린터를 구현하는 것이 이번 과제가 되었다.

 

큐를 구현하는 방법에는 여러 가지가 있겠지만, 가장 친숙한 배열로 먼저 큐 객체를 만들어보았다.

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;
  }
}

 기본적인 enqueue(), dequeue(), peek(), size() 메서드를 가진 큐 객체를 클래스로 구현하였다. 이를 활용하여 중요도를 고려한 큐 함수를 다음과 같이 구현해보았다. 

function solution(priorities, location) {
  let count = 0;
  const queue = new Queue();
  priorities.forEach((priority) => queue.enqueue(priority));

  while (queue.size() > 0) {
    const current = queue.dequeue();
    const max = Math.max(...queue.queue.slice(queue.front));
    if (current < max) {
      queue.enqueue(current);
    } else {
      count++;
      const currentIndex = (queue.front - 1) % priorities.length; 
      if (location === currentIndex) {
        return count;
      }
    }
  }
  return 0;
}

그런데 문제에서 주어진 테스트케이스 이외에, 채점을 돌리니 일부 케이스에서 실패가 떴다. 왜 그런지 여러 가지 테스트케이스를 추가해서 디버깅을 해보니, 프린트 된 요소들의 기존 인덱스 값이 정확하지 않는 문제가 발견되었다. 프린트 작업은 정상적으로 작동하지만, 이 과정에서 프린트된 값이 원래 몇 번째 인덱스였는지를 판단하는 과정에 문제가 있었던 것이다. 큐의 front값은 매번 변하며, 맨 앞에서 enqueue될 경우 순서가 맞지 않게 된다. 따라서 큐에 들어갈 배열 안에 값과 기존 인덱스가 pair로 함께 들어가도록 자료구조를 바꿔보았다. 또한 시간복잡도를 줄이기 위해, 사전에 우선순위들을 정렬해놓는 방법을 사용해보았다. 반목문 안에서 일일히 최댓값을 구하던 로직을 제거할 수 있었다. 

function solution(priorities, location) {
  const queue = new Queue();
  for (let i = 0; i < priorities.length; i++) {
    queue.enqueue([priorities[i], i]); // queue에 값과 인덱스를 넣어준다.
  }

  priorities.sort((a, b) => b - a); // 우선순위가 높은 것부터 내림차순으로 정렬

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

그 결과 기존의 인덱스가 보존된 채로 프린터가 정상작동하게 되었다. 

 

결론

• 큐를 배열로 손쉽게 구현할 수 있다. 
• JavaScript의 배열 안에는 다양한 형태의 객체가 들어갈 수 있으며, 당연하게도 배열을 추가할 수 있다. 
• 적재적소에 정렬을 사용하면 시간복잡도를 줄일 수 있다.