[JAVA]백준 1966번: 프린터 큐

 

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

1966번: 프린터 큐

 

1. 문제 설명

 

프린터 큐에 문서가 쌓인다..!

 

프린터는 다음과 같은 규칙으로 다음에 프린트할 문서를 정한다.

 

1. Queue의 가장 앞에 있는 문서의 중요도보다 중요도가 높은 문서가 있다면, 이 문서를 인쇄하지 않고 Queue 뒤에 배치한다. 

2. 가장 앞에 있는 문서가 중요도가 가장 높다면 인쇄를 한다.

 

중요도가 주어질때 우리가 알고 싶은 문서 X의 출력 순서를 몇 번째인지 구하는 문제이다.

 

2. 풀이

 

배열에 문서들의 중요도를 순서대로 저장한다.

제일 앞에 있는 문서를 head라고 한다면, head에서 부터 시작하여 문서 끝까지 순회하면서 head에 제일 가깝고, 우선순위가 높은 문서가 무엇인지 찾으면 된다.

 

그 문서를 찾았다면 우리가 원하는 X번째 문서인지 확인 후,

 

X번째 문서가 맡다면 출력 순서를 출력하고, 아니라면 찾은 문서의 중요도를 0으로 설정하여 가장 높은 우선순위를 찾을 때 검색되지 않도록 한다. (우선순위는 1부터 9 사이의 값만 존재하기 때문이다..!)

 

3. 코드

 

import java.io.*;
import java.text.DecimalFormat;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        int[] list = new int[102];

        for (int x = 0; x < test_case; x++) {
            int docs_num;
            int answer_position;
            int index=1;
            int head = 0;

            StringTokenizer input = new StringTokenizer(br.readLine());

            docs_num = Integer.parseInt(input.nextToken());
            answer_position = Integer.parseInt(input.nextToken());


            StringTokenizer list_input = new StringTokenizer(br.readLine());

            for (int y = 0; y < docs_num; y++) {
                list[y] = Integer.parseInt(list_input.nextToken());
            }

            while (true) {

                int max_num=0;
                int max_position=0;

                int y=head;
                do{
                    if (max_num < list[y]) {
                        max_num = list[y];
                        max_position = y;
                    }
                    y = (y + 1) % docs_num;
                }while(y!=head);

                if (max_position == answer_position) {
                    sb.append(index).append("\n");
                    break;
                }

                index++;
                list[max_position] = 0;
                head = max_position;
            }

        }

        System.out.println(sb);
        br.close();

    }
}