[백준] 1966 : 프린터 큐 - Java

• 백준 문제 URL
  

---

문제 접근

1. 문서를 하나 뽑는다.
2. 해당 문서의 중요도를 확인한다.
3. 남은 큐의 문서들의 중요도를 확인한다.
   • 중요도가 더 높은 문서가 있다면, 현재 문서를 큐의 뒤로 보낸다.
   • 중요도가 더 높은 문서가 없다면, 출력(=완료) 한다.
4. 큐의 구조 설계
   • 중요도 배열과 문서의 위치(index) 를 함께 관리해야 한다.
   • 즉, 중요도와 인덱스를 각각 별도의 큐로 구성하거나, (index, priority) 튜플 형태로 관리한다.

사전 환경 설정

배열	내용
[1, 1, 9, 1, 1, 1]	문서의 중요도(priority) 배열
[0, 1, 2, 3, 4, 5]	문서의 위치(index) 배열

시뮬레이션 진행 과정

단계	중요도 큐	인덱스 큐	동작	count
①	1 1 9 1 1 1	0 1 2 3 4 5	맨 앞(1)보다 큰 값(9) 존재 → 뒤로 이동	0
②	1 9 1 1 1 1	1 2 3 4 5 0	맨 앞(1)보다 큰 값(9) 존재 → 뒤로 이동	0
③	9 1 1 1 1 1	2 3 4 5 1 0	현재 문서(9)가 최댓값이므로 출력	1
④	1 1 1 1 1	3 4 5 1 0	최댓값이므로 출력	2
⑤	1 1 1 1	4 5 1 0	최댓값이므로 출력	3
⑥	1 1 1	5 1 0	최댓값이므로 출력	4
⑦	1 1	1 0	최댓값이므로 출력	5
⑧	1	0	마지막 문서 출력 (이미 목표 인덱스면 해당 단계에서 종료)	5 (마지막 카운트)

정리

• 문서의 중요도는 큐의 순서 유지를 전제로 확인해야 한다.
• 현재 문서보다 높은 중요도가 있으면 뒤로 보낸다.
• 큐의 front 문서가 가장 높은 중요도를 가질 때까지 반복한다.
• 출력되는 순서를 카운팅하여 특정 문서(index)의 인쇄 순서를 구할 수 있다.

---

제출

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));
        
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // 문서의 개수
            int M = Integer.parseInt(st.nextToken()); // 문서의 위치(index)

            Deque<int[]> dq = new ArrayDeque<>();

            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                dq.offer(new int[]{Integer.parseInt(st.nextToken()), j});
            }

            int count = 0;
            while (!dq.isEmpty()) {
                int[] now = dq.pollFirst();

                boolean isPrint = true;
                int size = dq.size();
                for (int j = 0; j < size; j++) {
                    int[] check = dq.pollFirst();
                    if (check[0] > now[0]) {
                        isPrint = false;
                    }
                    dq.offerLast(check);
                }

                if (isPrint) {
                    count++;
                    if (now[1] == M) {
                        System.out.println(count);
                        break;
                    }
                } else {
                    dq.offerLast(now);
                }
            }
        }
    }
}