문제
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
- 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
- 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 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);
}
}