[프로그래머스] 프린터 - Java

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

코딩테스트 연습 - 프린터

 

문제를 처음 읽을 때에는 단순히 priority queue 를 사용하여 해결하는 문제인 것 처럼 보였다.

하지만 내장된 PriorityQueue를 사용하려고 하면 다음과 같은 문제를 맞닥뜨리게 된다.

1. 동일한 priority를 가지는 elements의 순서가 unstable 하다.
2. 하나의 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;
    }
}