[BOJ] 백준 [1966] 프린터 큐 JAVA

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

1966번: 프린터 큐

문제

풀이

처음에 PriorityQueue를 쓰다가 33%쯤에서 틀렸다고 나왔다.
힙 구조특성상 맨 앞에있는 원소만 순서를 보장해줘서 그런 것 같다. 결론은 LinkedList 큐 에서 하나 뽑은 다음 , 더 높은 중요도의 문서가 있다면 그냥 큐의 뒤로 보내는 것이 가장 정석적인 방법일 것이다.

 

import java.util.*;
import java.io.*;
 
public class Main{
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        while(tc-->0){
            String[] input = br.readLine().split(" ");
            int N = Integer.parseInt(input[0]);
            int index = Integer.parseInt(input[1]);
 
            Queue<Document> queue = new LinkedList<>();
            input = br.readLine().split(" ");
            for(int i=0;i<input.length;i++){
                int priority = Integer.parseInt(input[i]);
                queue.add(new Document(i,priority));
            }
            int cnt=0;
            while(!queue.isEmpty()){
                Document poll = queue.poll();
                int before = queue.size();
                queue.stream()
                        .filter(doc->poll.priority < doc.priority) // 큐에 중요도가 더 높은 문서가 있는지 조사
                        .findAny().ifPresent(doc->{
                            queue.add(poll); // 존재한다면 뽑았던 문서를 다시 큐의 뒤로 보냄
                });
                if(queue.size()==before) { // 만약 남아있는 문서중 중요도가 제일 높다면
                    cnt++; // 카운트 증가
                    if(index == poll.docNum){ // 정답출력
                        System.out.println(cnt);
                        break;
                    }
                }
            }
        }
    }
}
class Document {
    int docNum;
    int priority;
 
    public Document(int docNum,int priority) {
        this.priority = priority;
        this.docNum = docNum;
    }
 
}