[백준] 1966. 프린터 큐 (Java)

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

1966번: 프린터 큐

 

 

풀이

0. 문제 해석

문제에 나온 규칙대로

 

1. 현재 Queue의 맨 앞의 문서 중요도 확인

2. 그 문서가 가장 중요도가 크거나 같은 문서라면 출력, 아니라면 맨앞 문서 맨 뒤로 보냄

 

위 과정을 반복하면 된다.

 

주의해야 할 것은 반복되면서 큐의 인덱스가 섞이기 때문에,

문제에서 요구하는 것이 궁금한 문서 1가지가 몇번째로 출력되는지 알려면 별도로 인덱스 값을 저장해야 한다.

 

 

1. 중요도와 인덱스 저장

인덱스 값을 따로 저장하기 위하여 2개의 큐를 사용하였다.

1개의 큐에 2차원 배열 형태로 집어 넣어도 된다.

 

2. 문서 출력 반복

이제 과정을 반복하며

몇 번째 인쇄인지 카운팅할 수 있는 count 변수를 활용해준다.

 

3. 전체 코드

// [백준] 1966. 프린터 큐 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
	static int t; // 테스트 케이스 수
	static int n; // 문서의 개수
	static int m; // 궁금한 문서의 초기 위치
	static Queue<Integer> queue; // 문서의 중요도
	static Queue<Integer> indexQueue; // 문서의 인덱스
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	t = Integer.parseInt(br.readLine());
    	
    	for(int i = 0; i < t; i++) {    		
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		n = Integer.parseInt(st.nextToken());
    		m = Integer.parseInt(st.nextToken());

    		queue = new LinkedList<>();
    		indexQueue = new LinkedList<>();
    		
    		st = new StringTokenizer(br.readLine());
    		// 중요도, 인덱스 입력
    		for(int j = 0; j < n; j++) {
    			queue.offer(Integer.parseInt(st.nextToken()));
    			indexQueue.offer(j);
    		}
    		
    		solve();
    	}
    }
    
    public static void solve() {
    	int count = 1; // 몇번 째 인쇄인지
    	
    	while (!queue.isEmpty()) {
    		int max = Collections.max(queue); // 현재 최우선 문서
    		int cur = queue.poll(); // 현재 문서
    		int curIndex = indexQueue.poll(); // 현재 인덱스
    		
    		// 인쇄 가능할 때
    		if(cur == max) {
    			// 찾는 문서를 인쇄했다면 몇번 째 인쇄인지 출력, break
    			if(curIndex == m) {
    				System.out.println(count);
    				break;
    			}
    			count++; // 인쇄할때마다 값 증가
    		}
    		// 인쇄 불가능하면 다시 맨 뒤에 넣어줌
    		else {
    			queue.offer(cur);
    			indexQueue.offer(curIndex);
    		}
    	}
    }
}