[백준] 1966번 프린터 큐 _ JAVA ( 주석 설명 )

풀이

1) 테스트케이스 T와 문서의 개수 N,  몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지 M을 입력받는다.


2) 각 문서의 중요도를 입력받는다.


3) Queue에 저장되어 있는 M번째 문서가 언제 출력되는지 추적해야되므로,

각 문서를 Queue에 저장할 때 int[] 배열로 (i번째 문서, 우선순위)를 같이 저장한다.


4) Queue.peek()가 우선순위가 가장 높은 문서일 때, Queue.poll()을 하면서 문서를 출력한다.

그렇지 않을 때는, Queue.peek()가 우선순위가 가장 높은 문서가 될 때까지 Queue.add(Queue.poll())을 반복한다.


5) 우선순위가 가장 높은 문서부터 출력이 될 때 count++ 을 해주며,

찾고자 하는 문서(우선순위를 통해 확인, front[1] == M )가 출력될 때 몇 번째로 출력되었는지 count를 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());



        for(int i=0;i<T;++i) { //테스트케이스만큼 반복
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); //문서의 개수
            int M = Integer.parseInt(st.nextToken()); //몇 번째로 인쇄되었는지 궁금한 문서가 현재 큐에서 몇 번째에 놓여 있는지

            //각 문서에 대한 '초기위치'와 '우선순위' 정보를 저장해야하므로 queue로 저장한다.
            //get() 사용 => LinkedList<>();
            LinkedList<int[]> queue = new LinkedList<>();

            //각 문서에 대한 '초기위치'와 '우선순위'를 입력받는다.
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; ++j) {
                int priority = Integer.parseInt(st.nextToken());

                int[] input = new int[2];
                input[0] = j; //초기위치
                input[1] = priority; //우선순위

                queue.add(input);
            }


            int count = 0; //몇 번째로 인쇄되는지 카운팅하기 위한 변수이다.

            //큐가 빈 값이 될 때까지 반복한다.
            //=> 몇 번째로 인쇄되었는지 궁금한 문서를 알면 바로 종료할 것이다.
            while(!queue.isEmpty()){
                //다른 큐 값들의 우선순위와 비교하기 위해, 큐에서 가장 처음 저장된 값을 불러온다.
                int[] front = queue.poll();

                //front 값이 우선순위가 가장 높은지 판별하기 위한 변수
                //우선순위가 가장 높으면, 인쇄 카운팅과 출력되는 문서의 초기위치가 문제가 궁금해하는 문서가 맞는지 확인한다.
                boolean isMax = true;


                for(int a=0;a<queue.size();++a){
                    if(front[1] < queue.get(a)[1]) { //front 값이 우선순위가 가장 높은 것이 아닐 경우

                        //front까지의 큐 값들을 전부 뒤로 add 해준다.
                        queue.add(front);
                        for (int b = 0; b < a; ++b) {
                            queue.add(queue.poll());
                        }

                        //front의 우선순위는 낮다.
                        //빠르게 break를 해주고 우선순위 비교를 반복한다.
                        isMax = false;
                        break;
                    }
                }

                if(!isMax){
                    continue;
                }

                count++; //front가 우선순위가 가장 높을 시 출력된다.
                if(front[0] == M) { //문제에서 찾고자 하는 M번째 문서의 출력 순서
                    sb.append(count).append('\n');
                    break;
                }
            }
        }

        System.out.println(sb);
    }
}