160. 1966(프린트 큐) - 자바

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

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i =0; i< T; i++) {
			String[] tmp = br.readLine().split(" ");
			int N = Integer.parseInt(tmp[0]);
			int M = Integer.parseInt(tmp[1]);
			Deque<Integer> importance = new ArrayDeque<>();
			Deque<Integer> index = new ArrayDeque<>();
			int cnt = 0;
			
			String[] impTmp = br.readLine().split(" ");
			for(int j = 0 ; j < N; j ++) {
				if(j == M) {
					importance.add(Integer.parseInt(impTmp[j]));
					index.add(-1);
				}
				else {
					importance.add(Integer.parseInt(impTmp[j]));
					index.add(j);
				}
			}
			
			
			while (true) {
				if (importance.peek() == Collections.max(importance)) {
					cnt ++;
					
					if(index.peek() == -1) {
						sb.append(cnt).append("\n");
						break;
					}
					else {
						importance.poll();
						index.poll();
					}
				}
				else {
					importance.add(importance.poll());
					index.add(index.poll());
				}				
			}			
		}
		System.out.println(sb);	
	}
}

문제요약

중요도가 높은 것부터 프린트를 하는데 선택한 프린트가 몇번째로 출력되는지 구하라.

설명

어떤식으로 돌아가는지를 먼저 이해해야한다.

예를 들어 6개의 프린트가 있고 0번째의 프린트를 해야한다고 하자.

그러면 0번째가 제일 앞에 있지만 중요도는 제일 높지 않아 맨 뒤 순위로 밀린다.

이런 식으로 반복하다 보면 중요도가 제일 높은 프린트 부터 출력하게 된다.

그 다음 모두 1이기 때문에 순서대로 출력을 하는데 결국 선택한 프린트물은 처음에 있었지만 5번째에 출력되게 된다.

 

			Deque<Integer> importance = new ArrayDeque<>();
			Deque<Integer> index = new ArrayDeque<>();

중요도와 인덱스를 따로 분리하였다.

 

하지만 값은 같이 받았다 ㅎㅎ

			String[] impTmp = br.readLine().split(" ");
			for(int j = 0 ; j < N; j ++) {
				if(j == M) {
					importance.add(Integer.parseInt(impTmp[j]));
					index.add(-1);
				}
				else {
					importance.add(Integer.parseInt(impTmp[j]));
					index.add(j);
				}
			}

 

				if(j == M) {
					importance.add(Integer.parseInt(impTmp[j]));
					index.add(-1);
				}

원하는 프린트는 인덱스 값을 범위내에 숫자가 아닌 다른 숫자 -1 로 표시했다.

 

				if (importance.peek() == Collections.max(importance)) {
					cnt ++;

만약 중요도에서 최대값이 맨 앞에 있다면 먼저 횟수를 한번 증가시킨다.

 

					if(index.peek() == -1) {
						sb.append(cnt).append("\n");
						break;
					}
					else {
						importance.poll();
						index.poll();
					}

그게 우리가 선택한 프린트물이라면 순서를 sb에 저장하고 반복문을 종료한다.

그렇지 않다면 그냥 중요도가 제일 높은 문서이므로 그 값을 제거해준다.

 

				else {
					importance.add(importance.poll());
					index.add(index.poll());
				}

만약 중요도가 제일 높지 않다면 그 값은 맨뒤로 보내진다.