[백준]JAVA - 1966번: 프린터 큐

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

1966번: 프린터 큐

🔶 풀이

Queue로 중요도만 체크해 주면 되는 간단한 문제다.

모든 문서를 FIFO 형식인 Queue에 입력해 놓고 중요도가 높은 것부터 순서대로 뽑아내면 된다.

 

언뜻 보면 정렬로 빠르게 뽑아낼 수 있을 것 같지만 중복된 중요도가 있을 수 있기 때문에 정렬로는 해결할 수 없다.

즉, Queue의 특성을 이용해서 해결해야 한다.

 

맨 앞에 있는 문서보다 중요도가 높은 문서가 있으면 맨 앞의 문서를 뒤로 보내고, 중요도가 제일 높다면 꺼낸다.

위와 같은 방법으로 M번째에 있는 문서가 몇 번째로 뽑히는지 찾아내면 된다.

 

위 예제에서 2번째 케이스 {1, 2, 3, 4}를 살펴보겠다.

 

[초기상태]

위 상태는 초기 상태로 M=2 다. 

즉, 중요도 3을 가진 문서가 몇 번째로 인쇄가 되는지 확인하면 된다.

 

cnt = 1

처음 문서의 중요도는 1, 다음 순서 중에서 보다 높은 중요도를 가진 문서가 존재하므로 맨 뒤로 이동

다음 문서의 중요도는 2, 다음 순서 중에서 보다 높은 중요도를 가진 문서가 존재하므로 맨 뒤로 이동

다음 문서의 중요도는 3, 다음 순서 중에서 보다 높은 중요도를 가진 문서가 존재하므로 맨 뒤로 이동

다음 문서의 중요도는 4, 가장 높은 중요도를 가진 문서이므로 인쇄.

 

cnt = 2

처음 문서의 중요도는 1, 다음 순서 중에서 보다 높은 중요도를 가진 문서가 존재하므로 맨 뒤로 이동

처음 문서의 중요도는 2, 다음 순서 중에서 보다 높은 중요도를 가진 문서가 존재하므로 맨 뒤로 이동

다음 문서의 중요도는 3, 가장 높은 중요도를 가진 문서이므로 인쇄.

 

M번째 문서가 2번째로 인쇄되었으므로 정답은 2

 

위와 같은 방식으로 코드를 짜면 된다.

큐에서 현재 맨 앞에 있는 문서의 중요도보다 높은 게 있는지 확인만 해주면 쉽게 해결할 수 있다.

 

<최종코드>

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        int tCase = Integer.parseInt(br.readLine()); // 테스트케이스 개수
	
        for (int i=0; i<tCase; i++) {
            st = new StringTokenizer(br.readLine());
			
            int N = Integer.parseInt(st.nextToken()); // 문서의 개수
            int M = Integer.parseInt(st.nextToken());
			
            Queue<int[]> q = new LinkedList<int[]>();
			
            st = new StringTokenizer(br.readLine());
			
            for (int j=0; j<N; j++) {
                int num = Integer.parseInt(st.nextToken());
				
                q.add(new int[] {j, num});
            }
			
            int cnt = 0;
            while (true) {
                int[] cur = q.poll();
                boolean chk = true; // 중요도가 높은 것이 있는지 여부
				
                for (int[] curQ : q) {
                    if (curQ[1] > cur[1]) {
                        chk = false;
                        break;
                    }
                }
                
                if (chk) {
                    cnt++;
                    if (cur[0] == M) break;
                } else {
                    q.add(cur);
                }
            }
			
            System.out.println(cnt);
        }
    }
}