👨‍💻 문제

---

✍️ 풀이

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.

2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면,
   이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

🤔 생각

사실 요구하는 구현은 어렵지 않다.
나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면
이라는 조건은 그냥 Queue의 요소들을 선형으로 탐색해보면 쉽게 알 수 있다.
시간 제한이 2초이며, N의 최대값 또한 100밖에 안 되기에
선형 탐색을 사용하여도 풀어지긴 할 것 같다.

하지만 선형 탐색은 기분이 나쁘다.
그리고 만약 N이 커진다면 효율은 기하급수적으로 나빠진다.

그렇기에 내가 사용한 것이 우선순위 큐이다.

📚 우선순위 큐

우선순위 큐를 사용하지 않고 정렬된 값을 가진 리스트나 배열을 사용하여도 좋다.
해당 문제의 경우 인덱스에 따른 탐색이 필요하지 않고,
값이 높은 것만 하나씩 뽑을 것이기에 필자는 우선순위 큐를 사용하였다.

결국 문서들이 인쇄되는 순서는
우선순위에 따른 내림차순이다.

하지만 단순히 이러한 정렬로 원하는 문서가 출력되는 순서를 알 수 없는 이유는,
같은 우선순위를 가진 문서들은 순서가 섞히게 될 수 있기 때문이다.

그렇다면 결국 큐를 한 번 움직여봐야 한다.
현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이라는 조건은
내림차순으로 정렬된 값을 가진 리스트나 배열 또는 큐를 통해 해결할 수 있다.

📚 큐

주어진 조건에 따라 큐를 제어해본다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.

2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면,
   이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

Document : 문서들의 우선순위 값과 인덱스 값을 가진 클래스
documents : Document들의 큐
documentPriorities : 문서들의 우선순위 값을 가진 우선순위 큐

        for (int i=0; true;) {
            Document d = documents.poll();
            if (d.priority >= documentPriorities.peek()) {
                documentPriorities.poll();
                i++;
                if (d.idx == findingDocumentIdx) {
                    return i;
                }
            }
            else {
                documents.add(d);
            }
        }

현재 출력하려는 문서의 우선순위 가치가 우선순위 큐의 첫 값보다 높거나 같다면 출력한다.
낮다면 뒤로 다시 재배치한다.

만약 출력한 문서가 출력 순서를 찾고 있는 문서라면, 몇 번째에 출력되는지 반환한다.
위 코드에서 몇 번째에 출력되는가에 대한 수치는 i이다.

---

📄 전체 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class _1966 {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static class Document {
        int priority;
        int idx;

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

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int t=0; t<T; t++) {
            sb.append(getResult());
            sb.append('\n');
        }

        System.out.print(sb);
    }

    private static int getResult() throws IOException {

        PriorityQueue<Integer> documentPriorities = new PriorityQueue<>(Collections.reverseOrder());
        Queue<Document> documents = new ArrayDeque<>();

        // input
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int findingDocumentIdx = Integer.parseInt(st.nextToken());

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

        // logic
        for (int i=0; true;) {
            Document d = documents.poll();
            if (d.priority >= documentPriorities.peek()) {
                documentPriorities.poll();
                i++;
                if (d.idx == findingDocumentIdx) {
                    return i;
                }
            }
            else {
                documents.add(d);
            }
        }
    }

}