[Programmers] 프린터

본 게시글은 PC 환경에서 보기 편하도록 설정이 되어 있습니다.

프린터

스택/큐 로 분류되어 있는 문제입니다.

우선순위 큐를 사용하고 우선순위 큐를 사용하기 위해 Comparable 의 compareTo 를 구현할 줄 안다면 쉬운문제입니다.

풀이 스타일

Java와 같은 객체지향 언어를 이용하여 알고리즘을 푼다면 객체지향스럽게 알고리즘을 풀어야 한다고 생각합니다.

단순한 알고리즘 풀이는 가독성은 당연히 떨어지고, Java를 쓰는 이유가 퇴색되는 것 같습니다.

따라서, Java를 이용해서 문제를 푸신다면 객체가 해야할 행동으로 문제를 풀 수 있도록 하시는 것을 추천드립니다.

Printer 객체는 두 개의 큐를 가지고 있습니다.

우선 순위가 가장 높은 document 를 head에 가지고 있는 PriorityQueue 와

프린터 사용자가 문서를 넣은 순서 그대로를 가지고 있는 일반적인 Queue 입니다.

우선순위 큐에 있는 Document 와 우선순위가 같은 Document 가 Queue 의 head에 위치한다면

Document 에 문서가 뽑힌 순서를 적어주고 List 로 관리합니다.

코드

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
 
        PriorityPrinter printer = makePrinter(priorities);
 
        List<Document> printedDocuments = getPrintedDocuments(priorities, printer);
 
        answer = findAnswer(printedDocuments, location);
 
        return answer;
    }
 
    private PriorityPrinter makePrinter(int[] priorities) {
        PriorityQueue<Document> documentPriorityQueue = new PriorityQueue<>();
        Queue<Document> documentQueue = new LinkedList<>();
 
        for (int time = 0; time < priorities.length; time++) {
            Document document = new Document(priorities[time], time);
            documentPriorityQueue.offer(document);
            documentQueue.offer(document);
        }
 
        return new PriorityPrinter(documentPriorityQueue, documentQueue);
    }
 
    private List<Document> getPrintedDocuments(int[] priorities, PriorityPrinter printer) {
        List<Document> printedDocuments = new ArrayList<>();
 
        for (int time = 1; time <= priorities.length; time++) {
            Document document = printer.print(time);
            printedDocuments.add(document);
        }
 
        return printedDocuments;
    }
 
    private Integer findAnswer(List<Document> printedDocuments, Integer location) {
        return printedDocuments.stream()
                .filter(document -> document.getInTime().equals(location))
                .findFirst()
                .orElseThrow(RuntimeException::new)
                .getOutTime();
    }
}
 
class PriorityPrinter {
    private PriorityQueue<Document> documentPriorityQueue;
    private Queue<Document> documentQueue;
 
    public PriorityPrinter(PriorityQueue<Document> documentPriorityQueue, Queue<Document> documentQueue) {
        this.documentPriorityQueue = documentPriorityQueue;
        this.documentQueue = documentQueue;
    }
 
    public Document print(int time) {
        //우선순위가 가장높은 문서라면
        if (documentPriorityQueue.peek().getPriority().equals(documentQueue.peek().getPriority())) {
            documentPriorityQueue.poll();
            Document document = documentQueue.poll();
            document.done(time);
            return document;
        }
        //우선순위가 가장 높은 문서가 아니라면
        return findHighPriorityDocument(time);
    }
 
    private Document findHighPriorityDocument(int time) {
        while (!documentPriorityQueue.peek().getPriority().equals(documentQueue.peek().getPriority())) {
            Document document = documentQueue.poll();
            documentQueue.offer(document);
        }
 
        documentPriorityQueue.poll();
        Document document = documentQueue.poll();
        document.done(time);
        return document;
    }
  
}
 
class Document implements Comparable<Document> {
    private Integer priority;
    private Integer inTime;
    private Integer outTime;
 
    public Document(Integer priority, Integer inTime) {
        this.priority = priority;
        this.inTime = inTime;
    }
 
    public Integer getPriority() {
        return priority;
    }
 
    public Integer getInTime() {
        return inTime;
    }
 
    public Integer getOutTime() {
        return outTime;
    }
 
    public void done(int time) {
        this.outTime = time;
    }
 
    @Override
    public int compareTo(Document document) {
        return document.getPriority().compareTo(this.getPriority());
    }
  
}