[알고리즘] 백준 1966번 : 프린터 큐 (실버3)

 

 

📌 문제

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

1966번: 프린터 큐

 

📌 알고리즘 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.StringTokenizer;

class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		Loop:
		while(T --> 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int N = Integer.parseInt(st.nextToken());  // 중요도
			int M = Integer.parseInt(st.nextToken());  // 원하는 문서 순서

			// 최대값 구하기 위한 배열
			Integer[] arr = new Integer[N];
			
			// [중요도, 순번]
			Deque<Integer[]> dq = new ArrayDeque<>();
			
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<N; i++) {
				int num = Integer.parseInt(st.nextToken());
				dq.offerLast(new Integer[] {num, i});
				arr[i] = num;
			}

			// 중요도 기준으로 내림차순
			 Arrays.sort(arr, Comparator.reverseOrder());
			 
			 for(int i=0; i<N; i++) {
				 
				 /**
				  * 프린터 첫 번째 요소의 중요도가 최댓값이 아닐 경우
				  */
				 while(dq.peekFirst()[0] != arr[i]) {
					 dq.offer(dq.pollFirst());
				 }
				 
				 
				 /**
				  * 프린터 첫 번째 요소의 중요도가 최댓값일 경우
				  */
				 // 원하는 순번일 경우
				 if(dq.peekFirst()[1] == M) {
					 bw.write(String.valueOf(i+1));
					 bw.write("\n");
					 continue Loop;
				 }
				 
				 // 원하는 순번이 아닐경우 그냥 출력만 한다.
				 dq.pollFirst();
			 }
		}
		bw.close();
	}
}