[백준] 1966번: 프린터 큐 - Java

문제

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

여러 문서가 프린터에 들어오면, 중요도에 따라 높은 중요도를 가진 문서부터 출력됩니다. 주어진 문서 리스트에서 특정 문서가 몇 번째로 출력되는지 계산하는 문제입니다. 중요도가 높은 문서를 먼저 출력하며, 특정 문서가 언제 출력되는지 순서를 찾는 것이 목표이다.

 

접근 방법

• 큐를 활용한 시뮬레이션: 문제에서 제시한 순서대로 문서를 처리하고, 인쇄 순서를 계산합니다. 큐를 이용해 앞에서부터 차례대로 문서를 꺼내고, 중요도가 더 높은 문서가 있으면 현재 문서를 다시 큐의 끝으로 이동시킵니다.
• 목표 문서 찾기: 문서를 인쇄할 때마다 해당 문서가 우리가 찾는 문서인지 확인하고, 찾고자 하는 문서가 인쇄되면 그 순서를 출력합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    static LinkedList<int[]> queue;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수

        while(T --> 0){
            queue = new LinkedList<>();

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

            int N = Integer.parseInt(st.nextToken()); // 문서의 수
            int M = Integer.parseInt(st.nextToken()); // 우리가 궁금해 하는 문서의 인덱스

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

            for(int i = 0; i < N; i++){
                queue.add(new int[]{i, Integer.parseInt(st.nextToken())}); // 문서의 인덱스와 중요도를 큐에 저장
            }

            sb.append(solution(M)).append("\n"); // 각 테스트 케이스의 결과를 sb에 저장
        }

        System.out.print(sb); // 결과를 한 번에 출력
    }

    static int solution(int M) {
        int findIt = 0; // 출력 순서 카운트

        while (!queue.isEmpty()) {

            int[] first = queue.poll(); // 큐에서 첫 번째 문서 꺼냄
            boolean isMax = true; // 현재 문서가 가장 높은 중요도를 가지는지 확인하는 플래그

            for (int i = 0; i < queue.size(); i++) {

                if (first[1] < queue.get(i)[1]) { // 현재 문서보다 높은 중요도를 가진 문서가 있는지 확인

                    queue.offer(first); // 현재 문서를 다시 큐의 끝으로 보냄

                    for (int j = 0; j < i; j++) {
                        queue.offer(queue.poll()); // 현재 문서보다 중요도가 낮은 문서들을 앞에 놓음
                    }

                    isMax = false; // 현재 문서가 가장 높은 중요도를 가지고 있지 않음을 표시
                    break;
                }
            }

            if (!isMax) {
                continue; // 중요도가 가장 높지 않다면 다음 루프로 넘어감
            }

            findIt++; // 문서 출력 순서 증가

            if (first[0] == M) { // 우리가 찾고자 하는 문서가 출력되는 경우
                break;
            }
        }

        return findIt; // 문서의 출력 순서를 반환
    }
}

 

메모리:15072kb 시간:124ms