백준/1966/Java - 프린터 큐

문제

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

1966번: 프린터 큐

---

문제에서 대놓고 알려 주듯, 큐를 활용하면 간단하게 구현할 수 있는 문제였다. 심지어는 큐가 무엇인지 몰라도 큐는 FIFO 방식의 자료 구조라는 설명까지 해주니 매우 친절한 문제. 

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

 복잡하게 생각할 것 없이 문제에서 주어진 위 조건을 그대로 코드로 구현하면 된다. 인쇄는 큐에서 poll을, 재배치는 poll 후 다시 add를 하면 된다. 

 문서의 중요도를 배열로 받을 수 있게 제시해주기 때문에 중요도 배열의 인덱스가 곧 각각의 문서라고 생각하고 큐에 집어넣어 주었다.

 

중요도 배열 = [1, 1, 9, 1, 1, 1]

큐 = [0, 1, 2, 3, 4, 5]    

-> 0번 문서의 중요도는 배열[0] 을 통해 알 수 있다.

 

큐를 돌면서 중요도를 확인하고 인쇄여부를 결정 후 인쇄를 하면 끝.

단 굳이 모든 문서를 다 인쇄할 필요 없이 문제에서 궁금해하는 M번 문서의 인쇄 순서를 구하면 반복을 멈추고 다음 테스트케이스로 넘어가면 된다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, ans;
	static Queue<Integer> q;
	static int[] arr;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		StringTokenizer st;
		//테스트케이스의 수. 
		int T = Integer.parseInt(br.readLine());
 		
		for(int i=0; i<T; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			//N : 문서의 개수 
			N = Integer.parseInt(st.nextToken()); 
			//M : 몇 번째로 인쇄되었는지 궁금한 문서의 인덱스 (친절하게도 문제에서 0번부터 시작함)
			M = Integer.parseInt(st.nextToken());
			//중요도 배열. 길이는 문서의 개수인 N이다.
			arr = new int[N];
			//문서가 들어있는 queue. 중요도 배열의 인덱스가 들어있다. 
			q = new LinkedList<>();
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				arr[j] = Integer.parseInt(st.nextToken());
				q.add(j);
			}
			print(M);
		}
		System.out.println(sb);
		
	}
	
	public static void print(int M) {
		int count = 0; //인쇄 번호. 
		while(!q.isEmpty()) {
			boolean isPrint = true; // 인쇄 가능 여부 확인.
			// 현재 큐의 가장 앞에 있는 문서의 중요도를 확인한다. 
			int idx = q.peek(); 
			int imp = arr[idx];
			for(int i=0; i<N; i++) {
				if(imp < arr[i]) isPrint = false; //현재 문서보다 중요도가 높은 문서가 1개라도 있다면 인쇄 불가. 
			}
			if(isPrint) { //인쇄가능하다면?
				q.poll(); //인쇄 -> 큐에서 나갑니다.
				arr[idx] = 0; // 인쇄를 했으니 중요도는 0. 
				count++;  //인쇄 번호 증가
				if(idx == M) {
					sb.append(count + "\n"); // 인쇄차례를 알고싶었던 M번째 문서였다면 여기서 종료. 
					return;
				}
			}else {//인쇄 불가능하다
				q.poll(); //큐에서 뺀 뒤,
				q.add(idx); //맨 뒤로 다시 넣는다. 
			}
		}
	}
}