JAVA 백준 1966 프린터 큐 (큐)

 

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

 

---

문제

1. 첫째 줄에 테스트 케이스의 수 T 가 입력된다.
2. 각 테스트 케이스는 총 두 줄로 이루어져 있으며, 첫째 줄에는 문서의 개수 N ( 1 <= N <= 100 ) 과 몇 번쨰로 인쇄되었는지 알아볼 문서가 현재 큐의 몇 번째에 있는지 나타내는 정수 M ( 1 <= M <= 10000 ) 이 공백으로 구분되어 주어진다. 둘째 줄에는 N개 문서의 중요도 ( 1 <= 중요도 <= 9, 중요도가 같은 문서가 있을 수 있음. ) 이 가 순서대로 공백으로 구분되어 주어진다.
3. 각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

---

 
 
초기 코드 (틀림)

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

public class Main {
    public static class Document {
        int importance;
        int number;

        public Document(int importance, int number) {
            this.importance = importance;
            this.number = number;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        StringBuilder sb = new StringBuilder();

        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());

            PriorityQueue<Document> queue = new PriorityQueue<>((o1, o2) -> o2.importance - o1.importance);
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                queue.offer(new Document(Integer.parseInt(st.nextToken()), j));
            }

            if (N == 1) {
                sb.append(1);
            } else {
                for (int j = 1; j <= N; j++) {
                    if (queue.poll().number == M) {
                        sb.append(j);
                        break;
                    }
                }
            }

            if (i <= T - 1) {
                sb.append("\n");
            }
        }

        System.out.println(sb);
    }
}

 
문서의 중요도로 내림차순 정렬한 PriorityQueue를 사용해서 풀어보았다.
문서의 원래 위치는 class를 만들어 PriorityQueue에 넣어 같이 정렬될 수 있도록 했다.
 
근데 생각해보니까 왜 이렇게 풀었는지 모르겠다.
중요도가 같을 때 순서가 원하는 대로 안 나올 텐데 왜 이렇게 풀었을까 싶다.
 
 
정답 코드

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

public class Main {
    public static class Document {
        int importance;
        int number;

        public Document(int importance, int number) {
            this.importance = importance;
            this.number = number;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        StringBuilder sb = new StringBuilder();

        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());

            Queue<Document> queue = new LinkedList<>();
            PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Comparator.reverseOrder());

            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                int num = Integer.parseInt(st.nextToken());
                queue.offer(new Document(num, j));
                maxQueue.offer(num);
            }

            if (N == 1) {
                sb.append(1);
            } else {
                int count = 1;
                while (!queue.isEmpty()) {
                    if (maxQueue.peek() == queue.peek().importance) {
                        if (queue.poll().number == M) {
                            sb.append(count);
                            break;
                        }
                        maxQueue.poll();
                        count++;
                    } else {
                        queue.offer(queue.poll());
                    }
                }
            }
            if (i < T - 1) {
                sb.append("\n");
            }
        }

        System.out.println(sb);
    }
}

 
큐 두 개를 이용해 만든 코드이다.
하나의 큐는 Queue를 입력한 순서대로 중요도와 입력된 순서를 쌍으로 갖는 클래스로 이루어진 큐이다.
다른 하나의 큐는 입력된 중요도를 원소로 갖는 내림차순으로 정렬된 PrioityQueue를 사용하였다.
 
내림차순 정렬한 PriorityQueue를 기준으로 Queue의 원소들과 비교하여 꺼낸 원소의 순서 번호가 M과 같을 때까지 진행한다.
같지 않을 땐 Queue의 수를 앞으로 빼서 뒤로 넣는 것을 반복한다.