#1966 : 프린터 큐

풀이방법

사용된 것:

Queue

정렬

 

2022.04.13

문서들의 우선순위들만을 따로 1차원 Integer 배열 ranks에 저장한 뒤,

이 배열을 내림차순으로 정렬하고, 가장 앞(ranks[0])부터 차례차례 방문하였다.

ranks 방문에 사용되는 인덱스 변수를 i라 하자.

 

가장 우선순위가 높은 문서 하나가 인쇄되면 i의 값을 1 증가시킨다.

그럼 방금 인쇄한 문서의 바로 다음으로 우선순위가 높은, 즉 이제 인쇄해야 하는 문서의 우선순위를 알 수 있다.

 

이제 인쇄해야 하는 문서의 우선순위 값을 cur이라 하고

현재 큐의 가장 앞에 있는 문서의 우선순위를 r이라 하자.

1. r == cur 이라면 인쇄를 하고,
2. r != cur 이라면 인쇄를 하지 않고 그 문서를 큐의 가장 뒤로 보낸다.

 

r == cur 이어서 인쇄를 할 때에

1. 이번에 인쇄한 문서가 문제에서 순서를 궁금해한 M번 문서일 경우, i의 현재 값에 1을 더한 값(i의 초기값이 1이 아닌 0이었으므로 1을 더해주어야 한다)을 화면에 출력하고 즉시 해당 테스트케이스를 종료한다.
2. 이번에 인쇄한 문서가 M번 문서가 아닐 경우 인쇄를 계속해나가야 한다. 큐에서 요소 하나를 poll()해주고 i의 값을 1 증가시킨다.

 

코드

Java(2022.04.13)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int t = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i<t; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			
			Queue<Paper> queue = new LinkedList<Paper>();	//문서정보 저장용 큐
			Integer[] ranks = new Integer[n];	//우선순위만 저장할 배열
			
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j<n; j++) {
				int temp = Integer.parseInt(st.nextToken());
				queue.add(new Paper(j, temp));
				ranks[j] = temp;
			}
			
			//우선순위를 내림차순으로 정렬
			Arrays.sort(ranks, Collections.reverseOrder());
			
			int index = 0;	//현재까지 인쇄한 문서의 개수이자, ranks배열을 가장 앞부터 탐색하기 위해 사용할 인덱스
			while(index<n) {	//n개 문서를 다 인쇄하면 무조건 테스트케이스 종료
				//현재 큐의 가장 앞에 있는 문서의 번호와 우선순위
				int num = queue.peek().num;
				int rank = queue.peek().rank;
				
				//큐 가장 앞의 문서를 인쇄해야 하는 경우
				if(rank == ranks[index]) {
					if(num == m) {	//m번 문서가 인쇄되었다면 그 문서의 번호를 출력하고 테스트케이스 종료
						sb.append((index+1) + System.lineSeparator());
						break;
					}
					queue.poll();	//큐에서 해당 문서 제거
					index++;	//다음으로 높은 우선순위로 이동
				}
				//큐 가장 앞의 문서를 큐의 가장 뒤로 옮겨야 하는 경우
				else {
					Paper p = queue.poll();
					queue.add(p);
				}
			}
		}
		
		System.out.print(sb);
		
	}

}

class Paper {
	int num;
	int rank;
	public Paper(int num, int rank) {
		this.num = num;
		this.rank = rank;
	}
}