[1966] 프린터 큐

 

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

---

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

// 1966 프린터 큐
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
	
		for(int i=0; i<tc; i++) {
			int N = sc.nextInt();
			int M = sc.nextInt();
			int cnt = 0;
			
			Queue<Integer> queue = new LinkedList<Integer>();
			Queue<Integer> alpha = new LinkedList<Integer>();
			
			int num = 0;
			for(int j=0; j<N; j++) {
				int a = sc.nextInt();
				queue.offer(a);
				alpha.offer(num++);
			}
			
			Outter : while(true) {
				int max = queue.peek();
				for(int j=1; j<queue.size(); j++) {
					if(max < ((LinkedList<Integer>) queue).get(j)) {
						int temp = queue.poll();
						int al = alpha.poll();
						queue.offer(temp);
						alpha.offer(al);
						continue Outter;
					}
				}
				int paper = queue.poll();
				int al = alpha.poll();
				cnt++;
				if(al == M) {
					System.out.println(cnt);
					break;
				}
			}
		}
	}
}

---

시뮬레이션 문제이다. 처음 문제를 풀 때에는 queue를 한개 사용하여 우선순위를 받았는데, 그렇게 풀게 되면 우선순위가 같을 수도 있기 때문에 어려움이 생긴다. 그래서 나는 queue를 2개 선언해서 한개에는 우선순위를 저장하고, 나머지 한개에는 우선순위에 해당하는 번호를 저장했다.

< 문제 풀이 >

1. queue에 우선순위를 넣는다.

2. alpha에 0부터 N-1 까지 인덱스 번호를 넣는다  6 0 / 1 1 9 1 1 1 을 예시로 들어보면 다음과 같이 queue 2개에 들어있는 상태이다. 0번째 인덱스의 있는 숫자가 언제 빠져나오는지 출력해야 한다.

alpha ->   0    1    2    3    4    5

queue ->  1    1    9    1    1    1 

3. 이제 queue의 제일 첫번째 인덱스를 나머지 인덱스랑 비교하는데 더 큰 인덱스가 있으면 pop하고 그 숫자를 다시 queue의 가장 뒤에 push한다. 그 다음 큐의 상태를 보자.

alpha ->   1    2    3    4    5    0

queue ->  1    9    1    1    1    1

4. 3의 과정을 한번 더 반복하게 되면 다음과 같다.

alpha ->   2    3    4    5    0    1

queue ->  9    1    1    1    1    1

5. 9가 우선순위가 가장 높기 때문에 pop을 해서 queue에서 없앤다.

alpha ->   3    4    5    0    1

queue ->  1    1    1    1    1

6. 이제 우선순위가 다 같으므로 한개씩 pop 하면서 alpha에서 pop하는 숫자가 M과 같은지 검사해서 몇번째로 나오는지 cnt변수를 선언해서 출력하면 된다.