[BOJ] 1966번 프린터 큐 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            Queue<Document> q = new LinkedList<>();
            int cnt = 0;

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                q.offer(new Document(i, Integer.parseInt(st.nextToken())));
            }

            while (!q.isEmpty()) {
                Document now = q.poll();

                int size = q.size();
                boolean isFirst = true;
                for (int i = 0; i < size; i++) {
                    if (q.peek().priority > now.priority) {
                        isFirst = false;
                    }
                    q.offer(q.poll());
                }

                if (isFirst) {
                    cnt++;
                    if (now.idx == M) {
                        sb.append(cnt).append("\n");
                        break;
                    }
                } else {
                    q.offer(now);
                }
            }
        }
        System.out.println(sb);
    }

    static class Document {
        int idx;
        int priority;

        public Document(int idx, int priority) {
            this.idx = idx;
            this.priority = priority;
        }
    }
}

📄 해설

접근

• 문제에서 주어진 설명 대로 따라가면 되는 문제이다. 큐를 사용해야하고, 필자처럼 클래스를 만들어서 사용해도 되는데, 싫으면 그냥 길이가 2인 정수배열을 사용해도 무방하다. 아마 이 경우가 메모리나 속도 측면에서 더 빠를 것이다.
• 문제에서 주어진 설명은 다음과 같다.
  1. 현재 큐의 맨 앞의 문서의 중요도를 확인한다.
  2. 현재 문서보다 중요도가 높은 문서가 있다면, 이 문서를 뒤로 보내고, 그렇지 않다면 인쇄를 한다.
• 1 과 2 의 과정을 통해 M 번째에 해당하는 문서가 몇번째로 인쇄되는지를 구하는 문제이다.

과정

• 테스트 케이스 T 를 입력 받고, 아래의 과정들을 반복한다.
• N 과 M 을 입력 받는다. 각각 문서의 개수, 몇번째로 인쇄되는지 알고 싶은 문서의 번호이다.
• N 개의 문서의 중요도를 입력 받으면서 몇번째 문서인지와 중요도를 클래스에 담고 큐에 넣는다.
• 큐가 빌 때까지 다음 과정을 반복한다.
  • 큐에서 원소 하나를 빼서 now 에 담고, 남은 원소들을 반복문을 통해 확인한다.
  • 큐에서 꺼낸 문서보다 중요도가 높은 문서를 발견한다면, isFirst 변수를 false 로 바꾼다. 그렇지 않다면 현재 큐의 맨앞에 있는 문서를 뒤로 보낸다. (지금 확인 중인 문서의 다음 문서이다.)
• 탐색이 끝난 후, isFirst 변수가 true 인 경우, 현재 문서의 중요도가 가장 높은 것이므로, cnt 값을 증가시키고, 현재 문서의 번호가 M 과 같은 값인지 확인한다.
• 같은 값이면 반복을 종료하고 출력한다.
• isFirst 변수의 값이 false 로 유지되고 있다면, 현재 문서를 다시 큐에 넣고 반복한다.