Q2 프린터 큐(1966번 문제)

백준

Q2 프린터 큐(1966번 문제)

mozzi329 2022. 7. 13. 23:11

728x90

📌 문제

문제)
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

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

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다. 여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력)
첫 줄에 테스트케이스의 수가 주어진다.
각 테스트케이스는 두 줄로 이루어져 있다.
테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력)
각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

📌 문제 분석❗️

먼저 예제의 입력을 통해 문제를 분석해보자.

입력	설명	출력
3	총 테스트 케이스 수	-
1 0	테스트 케이스 첫째 줄, 첫 번째 칸은 출력물 수, 두 번째 칸은 내가 관심있는 출력물의 인덱스	1
5	출력물의 우선순위 배열, 공백으로 나뉘어있기 때문에 적적히 입력 값을 받아야 한다.	1
4 2	테스트케이스 2 위의 설명과 동일	2
1 2 3 4	-	2
6 0	테스트케이스 3 위의 설명과 동일	5
1 1 9 1 1 1	-	5

위 사진은 테스트케이스 3번의 예시이다.

입력받는 우선순위 배열 중 가장 높은 수는 9이고, 내가 관심있는 출력물은 0번 인덱스이다. 출력은 우선순위가 가장 높은 순으로 진행되기 때문에 내가 관심있는 출력물은

1(0번 인덱스)

로 총 5번째에 출력이 일어나는 식이다.

❗️출력은 가장 우선순위가 높은 순부터 오른쪽 방향으로 진행된다.

출력물은 우선순위가 가장 높은 번호부터 오른쪽으로 진행된다. 방향이 정해져있고 먼저 들어오는 출력물이 가장 먼저 출력되는 출력되는 큐와 비슷하지만, 큐에 우선순위가 매겨져있다는 점에서 우선순위 큐(Priority Queue) 문제라고 생각할 수 있다.

※ 우선순위 큐(Priority Queue)

각 요소가 우선순위를 갖고 있는 자료구조로 더 높은 우선순위를 갖고 있는 요소들은 낮은 우선순위를 갖고 있는 요소들보다 먼저 사용된다.

📌 선언

변수 종류	변수 명	설명
BufferedReader	br	입력 값을 받기위한 BufferedReader 와 출력 값을 쌓기위한 BufferedWriter
BufferedWriter	bw	입력 값을 받기위한 BufferedReader 와 출력 값을 쌓기위한 BufferedWriter
int	N	총 테스트 케이스 횟수
Queue<QueueToken>	printQueue	자바 큐 링크드리스트 선언, QueueToken 객체는 인덱스와 우선순위 값을 저장한다.
QueueToken	qt	QueueToken 객체
StringTokenizer	st	출력 개수와 관심있는 인덱스 값이 입력으로 들어오는 String 을 분리해서 저장하기 위한 StringTokenizer
int	order	관심있는 출력물의 인덱스
int	numOfPrint	출력물의 개수
int	totalNumOfPrint	출력횟수
String []	tmp	split 메서드를 사용하기 위한 임시 String 배열
int []	priority	우선순위를 정렬하기 위한 배열, Arrays.sort() 메서드를 사용해 우선순위를 정렬해준다.

📌 진행

❗️우선순위 정렬 배열, 큐에 정렬되지 않은 우선순위 값 저장

            // tmp 배열과 Stream 클래스를 활용해 우선순위에 대한 int형 배열을 만들어준 뒤, 
            // Arrays.sort()메서드를 사용해 priority 배열을 정렬해준다. (default : 오름차순 정렬)
            priority = Stream.of(tmp).mapToInt(Integer::parseInt).toArray();
            Arrays.sort(priority);
            
            // 인덱스와 우선순위를 가지고 QueueToken 객체를 생성한 뒤, printQueue 에 담아준다.
            for (int j = 0; j < tmp.length; j++) {
                printQueue.add(new QueueToken(j, tmp[j].charAt(0) - '0'));
            }

우선 Stream 클래스를 사용해 받아온 입력 값은 인트형 배열로 만들어준 뒤, Arrays.sort() 메서드를 사용해 값을 정렬해준다. 그 뒤, 큐에 정렬되지 않은 배열의 값을 담아준다.

❗️우선순위에 따라 출력하기, 그리고 관심 출력물 찾기


            while (!printQueue.isEmpty()) {
                    qt = printQueue.poll();

                    if (priority[priority.length - 1 - totalNumOfPrint] == qt.prior) {
                        if (qt.idx == order) {
                            bw.write(totalNumOfPrint + "\n");
                            break;
                        }

우선순위가 정렬된 prior 배열에서 값을 하나씩 가져와 큐에서 뽑아낸 값의 우선순위와 비교한다.

만약, 우선순위가 같다면 출력물 갯수를 1 더해주고, 출력된 출력물이 내가 관심있는 출력물과 인덱스가 같은지 확인한다.

같을 경우 BufferedWriter에 문자열을 쌓아주고 break문으로 반복문(while문)을 탈출한다.

                    } else {
                        // 우선순위가 맞는 것을 못찾았다면 앞에서 하나 가져왔던 것을 도로 뒤에 붙여준다.
                        printQueue.add(qt);
                    }

우선순위가 다를 경우 빼냈던 QueueToken 객체를 다시 큐에 넣어준다.

❗️초기화

            // 문자열 버퍼를 쌓아 while 문을 탈출했다면 Queue를 초기화해준다.
            printQueue.clear();
            }

반복문(while문)에서 탈출했다면 큐를 비워준다.

❗️출력

쌓인 문자열 버퍼를 출력해준다.

📌 전체 코드

package level20_큐_덱_.Q4_1966;

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        Queue<QueueToken> printQueue = new LinkedList<>();
        StringTokenizer st;
        int order = 0;
        int numOfPrint ;
        int totalNumOfPrint;
        QueueToken qt;
        String [] tmp;
        int [] priority = {};

        for (int i = 0; i < N; i++) {
            totalNumOfPrint = 0;

            st = new StringTokenizer(br.readLine());
            numOfPrint = Integer.parseInt(st.nextToken());
            order = Integer.parseInt(st.nextToken());

            tmp = br.readLine().split(" ");
            if (numOfPrint == 1) {
                bw.write(1 + "\n");
                continue;
            }

            priority = Stream.of(tmp).mapToInt(Integer::parseInt).toArray();
            Arrays.sort(priority);
            
            for (int j = 0; j < tmp.length; j++) {
                printQueue.add(new QueueToken(j, tmp[j].charAt(0) - '0'));
            }

            while (!printQueue.isEmpty()) {                  
                    qt = printQueue.poll();

                    if (priority[priority.length - 1 - totalNumOfPrint] == qt.prior) {
                        totalNumOfPrint ++;
                        if (qt.idx == order) {
                            bw.write(totalNumOfPrint + "\n");
                            break;
                        }
                    } else {
                        printQueue.add(qt);
                    }
                }
            printQueue.clear();
            }

            br.close();
            bw.close();
        }

    public static class QueueToken{
        int idx;
        int prior;

        public QueueToken(int idx, int prior) {
            this.idx = idx;
            this.prior = prior;
        }

    }
}

티스토리