BOJ01966 프린터 큐

https://www.acmicpc.net/problem/1966 (opens new window)

프린터 기기는 인쇄하고자 하는 문서를 인쇄 명령을 받은 '순서대로', 즉 먼저 요청한 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO에 따라 인쇄가 되게 된다. 하지만 새로운 프린터기 내부 소프트웨어를 개발 했는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄하게 된다.

1. 현재 Queue의 가장 앞에 있는 문서의 '중요도'를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄한다.

현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다.

Document

문서의 중요도와 index 표현을 위한 Document 클래스이다.

static class Document {
    private int index;
    private int importance;

    public Document(int index, int importance) {
        this.index = index;
        this.importance = importance;
    }
}

제출 코드

현재 출력을 위한 문서가 가장 중요한 문서인지 확인한다.

boolean isImportant = true;

Document pollDocument = queue.poll();
for (Document document : queue) {
    // 자신 보다 중요한 문서가 있는 경우
    if (pollDocument.importance < document.importance) {
        isImportant = false;
        break;
    }
}

현재 문서가 target 문서인지, 중요도가 높은지 확인하고 인쇄 순서를 증가시킨다.

// 출력한 문서 index와 target이 같고 중요도가 가장 높은 경우
if (pollDocument.index == target && isImportant) {
    count++; // 출력
    break;
} else if (isImportant) { // 중요도만 높은 경우
    count++; // 출력
} else {
    queue.add(pollDocument); // 가장 뒤로 
}

아래는 최종 제출 코드이다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ1966 {

    static class Document {
        private int index;
        private int importance;

        public Document(int index, int importance) {
            this.index = index;
            this.importance = importance;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int t = scanner.nextInt();

        while (t-- > 0) {
            int n = scanner.nextInt(); // 문서의 개수
            int target = scanner.nextInt(); // 인쇄 순서를 알기위한 문서 index

            Queue<Document> queue = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                queue.add(new Document(i, scanner.nextInt()));
            }

            int count = 0;
            while (!queue.isEmpty()) {
                boolean isImportant = true;

                Document pollDocument = queue.poll();
                for (Document document : queue) {
                    // 자신 보다 중요한 문서가 있는 경우
                    if (pollDocument.importance < document.importance) {
                        isImportant = false;
                        break;
                    }
                }

                // 출력한 문서 index와 target이 같고 중요도가 가장 높은 경우
                if (pollDocument.index == target && isImportant) {
                    count++; // 출력
                    break;
                } else if (isImportant) { // 중요도만 높은 경우
                    count++; // 출력
                } else {
                    queue.add(pollDocument); // 가장 뒤로 
                }
            }
            System.out.println(count);
        }
    }
}

#algorithm #BOJ #구현 #자료 구조 #시뮬레이션 #큐