1. Problem 📃

[ 프린터 큐 ]

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

[ 문제 ]

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

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

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

2. Input 📇

[ 입력 ]

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

3. Output 📠

[ 출력 ]

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

4. Example 📚

[ 입출력 예시 ]

예제 입력	예제 출력
3 1 0 5 4 2 1 2 3 4 6 0 1 1 9 1 1 1	1 2 5

5. Solution 🔑

이번 문제에서 큐에 배열이 들어가는 것을 처음 알았다..

1. 테스트 케이스를 입력 받을 변수(T)를 선언하여 입력 받고 테스트케이스(T)만큼 반복한다.
   
   
2. 테스트 케이스마다의 큐(LinkedList)를 선언하는데 타입은 int형 배열로 한다.
   몇 번째 출력되는지 세어줄 변수(count)를 0으로 초기화하여 선언하고
   작업의 개수(N)과 작업들 중 몇 번째 위치하는지 알리는(M)을 입력 받는다.
   
   
3. LinkedList(q)에 작업량들을 담아주는데 이때, 담긴 순서랑, 우선도를 1차원 배열을 2칸 만들어서
   0번째 인덱스에는 처음 작업대에 담긴 위치를, 1번째 인덱스에는 우선도를 담아준다.
   
   
4. 큐가 빌 때 까지 계속 루프를 돌려준다.
   우선 가장 맨 앞 큐값을 저장할 배열 변수(front)하고 맨 앞 값이 우선순위가 가장 높다고 가정할 boolean변수를 true 값 설정한다.
   큐에서 실시간으로 가장 큰 값을 찾을 변수(highVal)과 그 값의 인덱스를 담을 변수(high)를 선언한다.
   
   
5. 큐를 돌면서 q에서 가져온 배열의 우선순위[1]가 front[1]보다 크다면 가장 크다고 판단했던 boolean변수를 false값으로 변경하고 q에서 가져온 배열의 우선순위[1] 값이 가장 큰 값이 실시간으로 변하는 highVal[1]보다 크다면 그 값이 가장 크다고 바꿔주고 몇 번째에 위치하는지 high변수에 저장한다.
   
   
6. 가장 큰 값이 아니였다면, 가장 큰 우선순위를 가진 위치 앞에 있던 값들은 모두 뒤로 넘겨주고 맨 앞 값을 poll하여 큐에서 제거하면서 count값을 올린다. 만약, poll하기 전에 맨 앞에 있는 값의 0번째 인덱스, 즉 큐에서 처음 위치[0] 값이 위에서 몇 번째 위치해 있는지 표시한 M값과 같다면 이 작업을 우선 처리해줘야하므로 count값을 증가시키고 무한루프를 빠져나오고 count값을 각 테스트케이스의 StringBuilder()마다 추가하여 개행한다.
   
   
7. 최종적인 StringBuilder()값을 출력한다.

6. Code 💻

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

public 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++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			LinkedList<int[]> q = new LinkedList<int[]>();
			
			int count = 0;
			
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			
			st = new StringTokenizer(br.readLine(), " ");
			
			for(int j=0; j<N; j++) {
				q.offer(new int[] { j, Integer.parseInt(st.nextToken()) } );
			}
		
			while(!q.isEmpty()) {
				
				// 가장 맨 앞 값을 저장함.
				int[] front = q.peek(); //{q.peek()[0], q.peek()[1]};
//				System.out.println(Arrays.toString(front));
				// 가장 크다는 가정을 시킴. 
				boolean Max = true;
				// 혹시나 제일 큰 값이 있다면 몇 번째 있는지.
				int[] highVal = q.peek();
				int high = 0;
				
				// 큐를 확인하면서 본인보다 큰 값이 있다면
				// Max를 false로 변경 후 가장 큰 값의 위치를 선정.
				for(int k=0; k<q.size(); k++) {
					
					if(q.get(k)[1] > front[1]) {
						Max = false;
						if(highVal[1] < q.get(k)[1]) {
							highVal = q.get(k);
							high = k;
						}
					}
				}
				// 가장 큰 값이 아니였다면, 앞의 값들을 모두 뒤로 offer.
				if(Max == false) {
					for(int j=0; j<high; j++) {
						q.offer(q.poll());
					}
				}
				// 뽑을 값의 인덱스가 초기 위치에 있던 값이랑 같다면
				// 개수를 증가시키고 종료하고 다음 케이스를 받을 준비.
				if(q.peek()[0] == M) {
					count++;
					break;
				}
				
				// 같지 않다면 그냥 뽑고 count값을 증가시킴.
				q.poll();
				count++;
			}
			sb.append(count).append("\n");
		}
		System.out.println(sb);
	}

}

7. Growth 🍄

그동안에는 Queue를 생성하거나 Stack을 생성하였는데 LinkedList를 통해 표현 할 수 있다는 점을 알았다.
또 큐 안에 배열을 이용하여 배열 형식의 값을 넣을 수 있다는 점도 알게되었다.

Q[0]	Q[1]	Q[2]	Q[3]
[0, 2]	[1, 4]	[2, 3]	[3, 1]

이런 식으로 넣을 수 있다.