Table of contents

프로그래머스 프린터

우선순위가 높은 페이지가 먼저 출력되는 프린터에서 지정된 페이지가 몇 번째로 출력되는지를 구하는 문제이다.

프린터 대기목록의 사이즈가 크지 않기 때문에, O(n^2)으로 풀어도 괜찮다.

private int print(int[] priorities, int location) {
    Printer printer = new Print(priorities);

    for (int i = 1; !Printer.isEmpty(); i++) {
        if (printer.print() == location) {
            return i;
        }
    }

    return -1;
}

class Printer {
    Queue<Page> queue = new LinkedList<>();

    public Print(int[] priorities) {
        for (int i = 0; i < priorities.length; i++) {
            queue.add(new Page(i, priorities[i]));
        }
    }

    public int print() {
        if (queue.isEmpty()) throw new IllegalStateException();
        Page page = queue.poll();

        if (!isFirst(page)) {
            queue.add(page);
            return print();
        }

        return page.location;
    }

    private boolean isFirst(Page target) {
        for (Page page : queue) {
            if (page.priority > target.priority) {
                return false;
            }
        }
        return true;
    }

    private boolean isEmpty() {
        return queue.isEmpty();
    }

    class Page {
        int location;
        int priority;

        public Page(int location, int priority) {
            this.location = location;
            this.priority = priority;
        }
    }
}

일반적인 큐를 대기열 목록 자료구조로 사용한다. 문제에서 주어진대로 대기열 목록에서 인쇄할 페이지 하나를 꺼낸 뒤, 해당 페이지보다 우선순위가 높은 페이지가 대기열 목록에 존재한다면 대기열의 끝에 해당 페이지를 넣고 다시 프린트를 시도한다. 만약, 해당 페이지가 가장 높은 우선순위를 가졌다면 인쇄하면서 location을 비교하면 된다. 물론 Printer와 Page 클래스를 만들지 않고 단순히 for 문을 이용하여 구현할 수도 있다.