문제 요약
중요도가 높은 문서를 우선 출력하는 프린터를 개발했다. 새롭게 개발한 프린터는 다음과 같은 방식으로 인쇄 작업을 수행한다.
1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼낸다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣는다.
3. 그렇지 않으면 J를 인쇄한다.
예를 들어 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 된다.
내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶다. 위 예제에서 C는 1번째로, A는 3번째로 인쇄된다.
제한사항
- 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
- 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
- location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.
예시
| priorities | location | return |
|---|---|---|
| [2, 1, 3, 2] | 2 | 1 |
| [1, 1, 9, 1, 1, 1] | 0 | 5 |
풀이과정
데브코스에서 한번 만났던 문제였고 이 때 Queue를 직접 만들어서 사용했기 때문에 이번에도 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++;
return value;
}
peek() {
return this.queue[this.front];
}
size() {
return this.rear - this.front;
}생성한 Queue에 기존 우선순위를 담아야 한다. 이 때 중요한 것은 문서도 같이 저장해야 한다는 것이다. 문서의 순서를 사용해서 내가 요청한 순서와 비교한 다음 몇 번째에 출력되는지 제출해야 한다.
const queue = new Queue();
for(let i = 0; i < priorities.length; i++) {
queue.enqueue([priorities[i], i]);
}문서의 중요도와 요청 순서를 Queue에 저장한다.
이 다음으로 진행할 사항은
1. Queue의 가장 첫 번째 문서보다 중요도가 높은 문서가 있을 경우 첫 번째 Queue는 가장 마지막으로 이동해야 하고. 가장 높은 중요도를 갖는 문서가 Queue의 첫번째에 올 때까지 반복해야 한다.
2. 1번 작업이 완료된 후 가장 첫 번째 Queue를 Queue에서 제거하고 프린트 횟수를 증가 한 다음. 1번 작업을 반복한다.
let cnt = 0;
while(true) {
const peek = queue.peek();
for(let i = queue.front; i < queue.rear; i++) {
if(peek[0] < queue.queue[i][0]) {
queue.enqueue(queue.dequeue());
break;
}
}
if(peek === queue.peek()) {
cnt++;
const rtV = queue.dequeue();
if(rtV[1] === location) {
return cnt;
}
}
}peek을 사용해서 가장 첫 번째 Queue를 얻어온다. 만약 현재 Queue에서 peek보다 중요도가 높은 문서가 있을 경우 가장 마지막으로 이동시킨다.
이 때 peek 값이 변경되기 때문에 밑에 if문은 동작하지 않는다. 따라서 다시 가장 중요도가 높은 문서를 찾는 for문을 반복한다. 최종적으로 반복문을 시행하기 전 peek 와 반복문을 시행한 후 peek 값이 일치할 경우 (문서가 모두 정렬된 상태) 카운트 값을 증가시키고 Queue에서 제거한다. 이때 출력한 문서가 내가 원하는 문서일 경우 카운트 값을 반환한다.
시간 초과?
입출력 예시는 모두 통과했지만 제출 했을 때 시간초과가 10개이상 발생했었다. 원인을 찾아보니 대기목록을 정렬하는 for문에서 무한루프가 발생하고 있었다. 문서를 추가하고 제거하는 작업이 포함되어 있기 때문에 queue.front, queue.rear 값이 계속 변했고 peek 값이 고정된 상태에서 계속해서 반복문을 실행했기 때문이다. 따라서 한 번만 실행할 수 있도록 break 문을 추가했다.
전체 코드
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++;
return value;
}
peek() {
return this.queue[this.front];
}
size() {
return this.rear - this.front;
}
dp() {
for(let i = this.front; i < this.rear; i++) {
console.log(this.queue[i])
}
}
}
function solution(priorities, location) {
const queue = new Queue();
for(let i = 0; i < priorities.length; i++) {
queue.enqueue([priorities[i], i]);
}
let cnt = 0;
while(true) {
const peek = queue.peek();
for(let i = queue.front; i < queue.rear; i++) {
if(peek[0] < queue.queue[i][0]){
queue.enqueue(queue.dequeue());
break;
}
}
if(peek === queue.peek()){
cnt++;
const rtV = queue.dequeue();
if(rtV[1] === location) {
return cnt;
}
}
}
}마무리
역시나 한 번 보았던 문제이지만, 직접 풀기보다 설명에 의존했기 때문에 처음 풀어본다는 느낌으로 시작했다. 이전에 Queue를 만들어서 사용했다는 기억에 사로잡혀서 Queue를 사용하지 않는 방법을 생각해보지는 않았다는게 아쉽다. 다른 분들의 풀이를 보니 정말 대단하신 분들이 많은거 같다...
