[백준] 1966번 프린터 큐(JAVA)

문제

- 프린터 기기는 인쇄하고자 하는 문서를 인쇄 명령을 받은 순서대로, 즉 먼저 요청된 것을 먼저 인쇄(FIFO, First In First Out)

- 상근이는 새로운 프린터기 내부 소프트웨어를 개발. 조건은 아래와 같음

   1. 현재 Queue의 가장 앞에 있는 문서의 중요도 확인

   2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤로

   3. 그렇지 않다면 바로 인쇄

- 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이 목표

 

해결방법

입력 받은 문서의 중요도와 인쇄 순서를 LinkedList에 저장하여 각 문서를 관리하도록 하였다. 처음 입력을 받으면서 M 번째에 있는 문서를 출력하는 순서를 알아내는 것이 목표이기 때문에 초기에 입력받은 순서를 함께 저장할 수 있도록 한 것이다.

Queue에서 동작하는 대로 처음 것을 뽑아낸 뒤 해당 문서의 중요도보다 높은 문서가 있으면 계속해서 뽑아내서 뒤에 다시 넣어줄 수 있도록 하였다. 이렇게 반복하면서 가장 큰 중요도를 가진 문서를 뽑아낼 때에는 count를 증가하여 몇 번째로 뽑아내는 것인지 알아낼 수 있도록 하였고, 뽑아내는 문서의 초기 위치가 M이라면 count를 출력할 수 있도록 하였다.

 

코드

import java.io.*;
import java.util.*;

class Main{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());		// 테스트 케이스 수

        for(int tc = 1; tc<=T; tc++){
            int count = 0;					// 몇 번째로 인쇄되는지 카운팅할 수 있는 변수
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());		// 문서의 개수
            int M = Integer.parseInt(st.nextToken());		// 몇 번째로 인쇄되었는지 궁금한 문서의 현재 위치
            LinkedList<int[]> queue = new LinkedList<>();	// 프린터 큐

            st = new StringTokenizer(br.readLine(), " ");
            for(int i = 0; i<N; i++){
            	// 초기 위치, 중요도 프린터 큐에 삽입
                queue.add(new int[] {i, Integer.parseInt(st.nextToken())});
            }

            while(!queue.isEmpty()){
                int[] first = queue.pollFirst();	// 첫 번째에 위치한 문서 정보
                boolean isMax = true;			// 중요도가 최대인지 판단하는 변수

                for(int i = 0; i<queue.size(); i++) {
                    // 중요도가 더 높은 문서가 존재한다면 아래와 같이 동작
                    if (first[1] < queue.get(i)[1]){
                        queue.add(first);		// 뽑아논 문서를 맨 뒤로 삽입
                        for(int j = 0; j<i ;j++){
                            // 중요도가 더 높은 문서 직전까지 존재하는 문서들을 다시 뒤로 삽입
                            queue.add(queue.pollFirst());
                        }
                        isMax = false;		// 지금 뽑아논 문서는 중요도가 가장 크지 않음
                        break;
                    }
                }

                if(!isMax) continue;			// 중요도가 가장 크지 않다면 다시 반복

                count++;				// 중요도가 크다면 프린트 진행 -> 인쇄 횟수 증가
                if(first[0] == M){			// 초기 위치가 원하는 M번째 문서라면
                    sb.append(count).append("\n");	// 인쇄 횟수 출력
                    break;
                }
            }
        }
        System.out.println(sb);
    }
}