알고리즘 문제/Programmers
[프로그래머스] 프린터 - Java
Praetoriani
2021. 3. 23. 22:32
문제 : programmers.co.kr/learn/courses/30/lessons/42587
코딩테스트 연습 - 프린터
일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린
programmers.co.kr
문제를 처음 읽을 때에는 단순히 priority queue 를 사용하여 해결하는 문제인 것 처럼 보였다.
하지만 내장된 PriorityQueue를 사용하려고 하면 다음과 같은 문제를 맞닥뜨리게 된다.
- 동일한 priority를 가지는 elements의 순서가 unstable 하다.
- 하나의 element를 poll 했을 때, 이 element보다 높은 priority를 가지는 element가 있다면 현재 선택된 element는 다시 queue에 offer되어야 한다. 즉, 처음 queue의 상태로부터 내 문서가 출력되기 까지(더 높은 priority를 가지는 문서가 모두 출력되기 까지) 내 문서와 같은 priority를 가지는 elements가 어떻게 queue에서 poll & offer되는지를 파악해야 한다.
이로 인해, 최초 예상처럼 문제가 간단히 풀리지 않아, 우선 가장 간단한 해결책으로 문제에서 주어진 동작방식을 그대로 수행하도록 코드를 작성해 보았다.
하나의 문서를 대기 queue에서 poll 할 때 마다 queue에 남아있는 문서들을 순회하며 priority를 확인하기 때문에 굉장히 비효율적인 방식이라서 제출시에 시간초과가 날 것으로 생각하였으나 테스트 케이스가 심플한 것들 뿐인지 의외로 통과가 되었다.
소스코드
import java.util.ArrayDeque;
import java.util.Iterator;
public class Solution {
public int solution(int[] priorities, int location) {
ArrayDeque<Document> queue = new ArrayDeque<>();
for (int i = 0; i < priorities.length; i++) {
queue.offer(new Document(i == location, priorities[i]));
}
int count = 0;
while (!queue.isEmpty()) {
Document doc = queue.poll();
if (!isPrintable(doc, queue)) {
queue.offer(doc);
continue;
}
count++;
if (doc.isMine()) {
return count;
}
}
return -1; // error
}
boolean isPrintable(Document doc, ArrayDeque<Document> queue) {
int docPriority = doc.getPriority();
Iterator<Document> iter = queue.iterator();
while (iter.hasNext()) {
if (docPriority < iter.next().getPriority()) {
return false;
}
}
return true;
}
}
class Document {
private final boolean isMine;
private final int priority;
Document(boolean isMine, int priority) {
this.isMine = isMine;
this.priority = priority;
}
public boolean isMine() {
return this.isMine;
}
public int getPriority() {
return this.priority;
}
}