[백준] 1966번. 프린터 큐(JAVA)

문제

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

---

풀이(18분)

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));
        StringTokenizer st;

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

        for(int i = 0; i < t; i++){
            Queue<Check> queue = new LinkedList<>();
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            ArrayList<Integer> priorityList = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++){
                int priority = Integer.parseInt(st.nextToken());
                priorityList.add(priority);
                if(j == m){
                    queue.add(new Check(true, priority));
                    continue;
                }
                queue.add(new Check(false, priority));
            }
            Collections.sort(priorityList);
            int answer = 1;
            int idx = priorityList.size() - 1;
            while(true){
                Check check = queue.poll();
                if(check.priority < priorityList.get(idx)){
                    queue.add(check);
                    continue;
                }
                if(check.answer){
                    System.out.println(answer);
                    break;
                }
                answer++;
                idx--;
            }
        }
    }

    public static class Check{
        boolean answer;
        int priority;

        public Check(boolean answer, int priority){
            this.answer = answer;
            this.priority = priority;
        }
    }
}

 

Check 클래스는 정답을 출력해야하는 순번에 대한 값이였는지와, 우선도를 가진 값을 저장하는 클래스이다.

 

문제 풀이 순서는 다음과 같다.

1. 입력을 받은 것을 모두 큐에 넣는다.

1-1. 입력을 받으며 넣을 때 우선도에 대한 값을 따로 저장해둔다.

2. 우선도를 정렬하여 높은 순서부터 나오게 만든다.

3. 큐를 순환하며 우선도가 높다면 뽑아내고, 그렇지 못하다면 다시 큐에 추가한다.

3-1. 뽑아내는 과정에서 정답을 출력해야 한다면 출력하고 반복문을 멈춘다.