[Java] 백준 프린터 큐

1. 문제 분석

기존 프린터처럼 들어온대로 출력하는 것이 아니라 우선순위에 따라 출력을 한다고 한다.

또한 우선순위는 주어지고 높은 순서부터 뽑는다고 한다.

 

나는 여기서 우선순위 큐가 바로 떠올랐다. 우선순위 대로 데이터를 뽑아주면 끝이니깐 매우 쉬운문제라고 생각했다.

하지만 정렬이 안된다.. 그리고 역순으로 정렬을 해야하는데 구현하는게 상당히 까다로웠다.

 

결국 마지막으로 생각한 것이 일반 큐에 데이터를 넣고 하나씩 비교를 하는 방법으로 구현했다.

만약 내가 뽑고자 하는 우선순위가 아니라면 다시 큐에 넣고 우선순위면 해당 위치를 주었다.

2. 구현

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        //BufferedReader 로 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
        //결과값을 위한 StringBuilder
        StringBuilder sb = new StringBuilder();

        //전체 반복 수
        int count = Integer.parseInt(br.readLine());
        for (int i = 0; i < count; i++) {

            //0 -> 문서 순서, 1 -> 우선 순위
            Queue<int[]> q = new LinkedList<>();
            // 찾고자 하는 프린트의 위치 -> 하나씩 비교하면서 찾음
            int checkIdx = 0;

            //입력
            StringTokenizer st = new StringTokenizer(br.readLine());

            //전체 프린트물의 개수와 찾고자 하는 프린터의 위치 -> 우리가 찾고자 하는 프린터의 위치
            int totalPrintCount = Integer.parseInt(st.nextToken());
            int printIdx = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            //데이터 넣어줌 -> 넣는 순서, 우선 순위
            for (int j = 0; j < totalPrintCount; j++) {
                q.offer(new int[]{j, Integer.parseInt(st.nextToken())});
            }

            while (true) {
                //큐에서 데이터를 하나 가져옴
                int[] nowPrint = q.remove();
                boolean isMax = true;

                //큐 탐색
                for (int[] printInfo : q) {
                    //현재 큐에서 뽑은 데이터보다 더 높은 우선순위를 가진 큐가 존재한다면?
                    if (printInfo[1] > nowPrint[1]) {
                        isMax = false;
                        break;
                    }
                }

                //지금 맨앞에 있는 것이 가장 높은 우선순위
                if (isMax) {
                    checkIdx++;
                    //내가 뽑고자 하는 것이라 맞는다면?
                    if (nowPrint[0] == printIdx) {
                        sb.append(checkIdx).append("\n");
                        break;
                    }
                }
                //아니라면 다시 데이터를 넣어줌
                else {
                    q.offer(nowPrint);
                }
            }
        }
        System.out.println(sb);
    }
}

입력을 받는 부분은 나중에 한번에 포스팅할려고 한다.

큐에 데이터를 전부 넣어주고 이제 뽑고자하는 것에 맞는지 확인을 한다.

 

현재 큐의 맨 앞에 있는 데이터를 remove하고 그 데이터의 우선순위가 가장 높은지 확인한다.

만약 높다면 우선순위 정렬이 안된 상태이므로 다시 큐를 넣어준다.

 

이번에는 뽑을려고 하는 큐의 데이터가 우선순위가 가장 높다고 생각해보자.

뽑을려는 위치가 동일하다면 그게 답이되는 것이고 아니라면 checkIdx를 증가시켜 다음 Index로 넘어가면 된다.

 

그렇다면 우선순위가 동일하면 어떻게 처리를 할까?

테스트 3을 보면 1 1 9 1 1 1이 우선 순위가 된다. 이것을 큐에 넣어주면 (0, 1), (1, 1), (2, 9), (3, 1), (4, 1), (5, 1)이 된다.

이제 while loop를 돌려보자. 처음은 우선순위가 낮으니 다시 큐에 들어간다.

 

1st -> (1, 1), (2, 9), (3, 1), (4, 1), (5, 1), (0, 1)  checkIdx = 0

2nd -> (2, 9), (3, 1), (4, 1), (5, 1), (0, 1), (1, 1)  --> 다음 루프에서는 isMax가 true가 된다. checkIdx = 0

3rd -> (3, 1), (4, 1), (5, 1), (0, 1), (1, 1)  remove된 큐의 데이터는 다시 offer되지 않는다. checkIdx = 1

4th -> (4, 1), (5, 1), (0, 1), (1, 1) 마찬가지로 remove된 데이터는 offer가 안됨, checkIdx = 2

5th -> (5, 1), (0, 1), (1, 1) checkIdx = 3

6th -> (0, 1), (1, 1) checkIdx = 4

7th -> (1, 1)  remove된 큐의 데이터 중 idx와 printIdx가 동일하다. checkIdx = 5가 답이 된다.

 

이런 식으로 Idx를 구분하면 된다.

3. 마무리

사실 우선순위 큐로 구현하고 싶어 삽질을 좀 했다.

암만봐도 저걸 그냥 큐로 데이터 넣고 하는 방식은 너무 비효율적이라고 생각을 했다.

근데 그게 답이라니.. 알고리즘 풀때는 이거다 싶으면 해야겠다..