[코딩테스트/백준 알고리즘] 1966번 : 프린터 큐 (Java, 자바 풀이)

문제

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

1966번: 프린터 큐

---

문제 설명

---

문제 이해

큐를 사용하면 쉽게 해결할 수 있는 문제다.

 

맨 마지막 테스트 케이스인

6 0 
1 1 9 1 1 1

에 대해 분석해보자.

테스트 케이스를 입력받은 큐의 상태는 위와 같다.

---

우선 순위가 가장 높은 2번 문서가 큐의 맨 앞에 올때까지 그 외 문서는 큐의 맨 뒤로 옮긴다.

우선 순위가 가장 높은 2번 문서가 큐의 맨 앞에 왔다면 문서를 인쇄한다.

---

이후 문서들의 우선순위는 모두 같기 때문에 큐의 맨 앞에 있는 문서부터 차례대로 인쇄한다.

0번 문서는 다섯번째 순서로 인쇄되는 것을 볼 수 있다.

---

문제 풀이

자료구조

class File {
    public int id;	//문서 번호
    public int imp;	//우선 순위

    File(int id, int imp) {
        this.id = id;
        this.imp = imp;
    }
}

문서의 정보를 담고 있는 File 클래스를 따로 만들어서 문서의 번호와 우선 순위를 관리했다.

 

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        while(t-- > 0) {
            Queue<File> q = new LinkedList<>();	//큐
            int n = sc.nextInt();	//문서의 수
            int m = sc.nextInt();	//추적하는 문서의 번호
            int[] important = new int[10];
            int count = 0;	//인쇄된 문서의 수
            
            for(int i = 0; i < n; i++) {
                int imp = sc.nextInt();
                q.offer(new File(i, imp));
                important[imp]++;
            }

 배열 important는 우선순위 별로 문서가 몇 개가 있는지 기록하는 역할을 한다.

 큐에 있는 가장 높은 우선순위의 문서를 인쇄하기 전까진 그보다 낮은 우선 순위의 문서는 인쇄될 수 없기 때문에 현재 문서보다 높은 순위의 문서가 있는지 확인하는 작업을 해주어야 한다. 이 때 사용한다.

 

ex)

6 0

1 1 9 1 1 1의 important 배열 초기 값

idx	1	2	3	4	5	6	7	8	9
important[idx]	5	0	0	0	0	0	0	0	1

---

코드

import java.util.*;

class File {
    public int id;	//문서 번호
    public int imp;	//우선 순위

    File(int id, int imp) {
        this.id = id;
        this.imp = imp;
    }
}

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        while(t-- > 0) {
            Queue<File> q = new LinkedList<>();
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] important = new int[10];
            int count = 0;

            for(int i = 0; i < n; i++) {
                int imp = sc.nextInt();
                q.offer(new File(i, imp));
                important[imp]++;
            }

            while(true) {
                File f = q.poll();
                boolean cp = true;	//인쇄 가능 여부
                
                for(int i = f.imp + 1; i < 10; i++) {	//f보다 우선 순위가 높은 문서가 있는지 확인
                    if(important[i] > 0) {	//고 우선순위의 문서가 있으면
                        cp = false;	//인쇄 불가 처리
                        break;
                    }
                }
                if(cp) {	//인쇄가 가능할 때
                    count++;
                    important[f.imp]--;

                    if(f.id == m) {	//f가 추적하는 문서의 번호일 때
                        System.out.println(count);
                        break;
                    }
                }
                else {	//인쇄가 불가할 때
                    q.offer(f);	//큐의 맨 뒤로 f를 옮김
                }
            }
        }
    }
}