BOJ - 1966

1. 문제

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

2. 풀이

큐를 활용할 줄 아는지 묻는 문제이다. 우선순위와 문서의 인덱스를 담는 클래스를 생성한 후 Queue에 넣는다. 우선순위가 가장 높은 것부터 뽑기 위해 정렬 후 출력할 우선순위와 맞지 않는 문서는 뒤로 보내도록 구현하였다.

import java.util.*;

public class Main1966 {
    static int T;
    static class Document{
        public int priority;
        public int sequence;

        Document(int p, int s){
            priority = p;
            sequence = s;
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        for(int t = 0; t < T; t++){
            ArrayList<Integer> ranks = new ArrayList<>();
            Queue<Document> que = new LinkedList<>();
            int N = sc.nextInt();
            int M = sc.nextInt();
            for(int i = 0; i < N; i++){
                int rank = sc.nextInt();
                que.add(new Document(rank, i));
                ranks.add(rank);
            }
            ranks.sort(null);
            int index = ranks.size()-1;
            int count = 1;
            while(!que.isEmpty()){
                Document present = que.poll();
                if(present.priority < ranks.get(index)){
                    que.offer(present);
                }
                else{
                    if(present.sequence == M)
                        break;
                    count++;
                    index--;
                }
            }
            System.out.println(count);
        }
    }
}

3. 적용된 알고리즘

큐