알고리즘 프린터
2024. 4. 4. 08:35ㆍ카테고리 없음
import java.io.*;
import java.util.*;
public class Main {
// Process 클래스로 문서의 priority랑 sequence를 저장
private static class Process {
int priority;
int sequence;
Process(int priority, int sequence) {
this.priority = priority;
this.sequence = sequence;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testNum = Integer.parseInt(br.readLine());
while (testNum> 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
//n으로 문서의 개수를 받고 몇번쨰로 인쇄됬는지 궁금한 문서 위치를 location으로 받음
int n = Integer.parseInt(st.nextToken());
int location = Integer.parseInt(st.nextToken());
int cnt = 0;
Queue<Process> Q = new LinkedList<>();
PriorityQueue<Integer> PQ = new PriorityQueue<>(Collections.reverseOrder());
st = new StringTokenizer(br.readLine());
//문서의 중요도를 입력받아 큐에 넣음
//이후 큐에서 문서 중요도랑 순서 저장
for (int i = 0; i < n; i++) {
int priority = Integer.parseInt(st.nextToken());
Q.offer(new Process(priority, i));
PQ.offer(priority);
}
//큐에서 문서를 꺼낸다음 문서가 중요도가 가장 높은애랑 비교해서 같거나 높으면 우선순위 큐에서
//빼준다음 몇번쨰로 인쇄되는지 카운트를 증가시킨다. 이후 처음에 입력한 궁금한 문서랑 순서가 같으면
//몇번쨰로 인쇄됬는지 sout해주고 종료시킴. 이외의 경우에 다시 큐에 넣어줌(else부분)
while (true) {
Process p = Q.poll();
if (p.priority >= PQ.peek()) {
PQ.poll();
cnt++;
if (p.sequence == location) {
System.out.println(cnt);
break;
}
} else {
Q.offer(p);
}
}
testNum--;
Q.clear();
PQ.clear();
}
br.close();
}
}
//메모리 14932 시간: 166ms
프라이어티큐로 우선순위를 저장하고 꺼내준다. 프라이어티큐가 동일한 우선순위를 가졌을경우 먼저 입력된 값부터 꺼내온다