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

백준 1966번 문제 - 프린터 큐 

1966번: 프린터 큐

---

문제 분석

 

 

• 큐에 N개의 숫자가 순서대로 입력되어 있다.
• 큐에서 숫자를 poll할 때 숫자의 중요도가 가장 높을 경우 출력하고, 아닐 경우 맨 뒤로 보낸다.
• 이 때 , N개의 수 중 M번째로 입력되는 숫자가 출력된느 순서를 출력해라.

---

 

해결 키 포인트

 

• 우선순위와 순서를 담을 수 있는 클래스 생성
  • 클래스 인스턴스는 우선순위(important)와 순서(index)
• 숫자가 담겨진 리스트를 정렬한다.
  • 우선순위가 높은 거(큰 수)를 먼저 ! 
  • 우선순위가 동일할 경우 index가 빠른 것(작은 수)을 먼저 !

---

코드

 

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

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

        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            ArrayList<Node> nums = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                nums.add(new Node(i, Integer.parseInt(st.nextToken())));
            }

            int i = 0;
            int count = 0;
            while(nums.size() > 0) {
                int max = Collections.max(nums).important;
                Node value = nums.get(i);
                if(max == value.important) {
                    if(value.index == M) {
                        System.out.println(count+1);
                        break;
                    }
                    else {
                        nums.remove(value);
                        count++;
                        if(i > nums.size()-1) {
                            i = 0;
                        }
                    }
                }
                else {
                    i = (i+1) % nums.size();
                }
            }

        }
    }

    public static class Node implements Comparable<Node> {
        int important;
        int index;

        public Node(int index, int important) {
            this.index = index;
            this.important = important;
        }

        @Override
        public int compareTo(Node o) {
            if(important == o.important) {
                return index - o.index;
            }
            return important - o.important;
        }
    }
}