프린터 큐

문제

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

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

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

첫 줄에 test case의 수가 주어진다. 각 test case에 대해서 문서의 수 N(100이하)와 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만)이 주어진다. 다음줄에 N개 문서의 중요도가 주어지는데, 중요도는 적절한 범위의 int형으로 주어진다. 중요도가 같은 문서가 여러 개 있을 수도 있다. 위의 예는 N=4, M=0(A문서가 궁금하다면), 중요도는 2 1 4 3이 된다.

출처 : https://www.acmicpc.net/problem/1966

*풀이 

 

 1. 출력이 이루어 진다는 것은 큐에 자신 보다 큰 수가 존재 하지 않는다는 것이다

 2. 출력이 이루어질때 순서를 1씩 증가시키고 그 출력물이 몇번째 출력물인지 궁금해 하는 프린트라면 반복문을 그만 돈다 

 

*전체 Source Code

package test;

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;

import java.util.Stack;

public class Main {

public Node rear, front;

public int size;

public int oper(int[] priorities , int position) {

clear();

int print = 0;

// 큐에 모든 수 넣기

for(int i = 0; i < priorities.length; i++) {

Document doc;

if(i == position)

doc = new Document(priorities[i], true);

else 

doc = new Document(priorities[i], false);

enqueue(doc);

}

while(true) {

boolean exist = false;

int popNum = front.doc.data;

boolean popPrint = front.doc.print;

//큰수 있는지 찾기

Node temp = front;

for(int i = 0; i < size; i++) {

if(temp.doc.data > popNum) {

exist = true;

break;

}

temp = temp.next;

}

// 출력하려는 놈보다 큰수가 있는경우 dequeue enqueue

if(exist == true)

enqueue(dequeue());

//큰수가 없는경우 dequeue하면서 print++;

else {

//dequeue를 하고 true인지 확인하면 오류

print++;

//dequeue 할때 print가 true면 그만

if(popPrint == true)

break;

dequeue();

}

}

return print;

}

public void clear() {

rear = null;

front = null;

size = 0;

}

public void print() {

Node temp = front;

while(temp != null) {

System.out.print(temp.doc.data);

if(temp.next != null) 

System.out.print(" -> ");

temp = temp.next;

}

}

public Document dequeue() {

if(front == null)

return null;

Document temp = front.doc;

front = front.next;

if(front == null) 

rear = null;

size--;

return temp;

}

public void enqueue(Document data) {

Node node = new Node(data);

if(rear == null) {

rear = node;

front = node;

}

else {

rear.next = node;

rear = node;

}

size++;

}

static class Document{

public int data;

public boolean print;

public Document(int data, boolean print) {

this.data = data;

this.print = print;

}

}

class Node {

public Node next;

public Document doc;

public Node(Document doc) {

this.doc = doc;

}

}

public static void main(String[] args) {

// TODO Auto-generated method stub

Main test = new Main();

Scanner sc = new Scanner(System.in);

List<Integer> results = new ArrayList<>();

//테스트 케이스 만큼

int num = Integer.parseInt(sc.nextLine());

String[] first = new String[2];

for(int i = 0; i < num; i++) {

// 문서 수 , 출력물 번째수 

first = sc.nextLine().split(" ");

int docNum = Integer.parseInt(first[0]);

int docPosition = Integer.parseInt(first[1]);

// 각문서의 우선순위

String[] second = new String[docNum];

int[] priorities = new int[docNum];

second = sc.nextLine().split(" ");

for(int j = 0; j < docNum; j++) 

priorities[j] = Integer.parseInt(second[j]);

results.add(test.oper(priorities, docPosition));

}

for(int result : results)

System.out.println(result);

}

}