알고리즘 프린터

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

 

프라이어티큐로 우선순위를 저장하고 꺼내준다. 프라이어티큐가 동일한 우선순위를 가졌을경우 먼저 입력된 값부터 꺼내온다