[Java][백준] #1966 - 프린터 큐

🔗 백준 1966 - 프린터 큐

문제

알고리즘 분류

• 구현
• 자료 구조
• 시뮬레이션
• 큐

---

풀이

1. 입력 (Queue)

• 인덱스를 저장하는 큐와 중요도를 저장하는 큐 각각 만들어 저장

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        for(int i = 0; i<t; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            docNum = Integer.parseInt(st.nextToken());
            target = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            priorQ = new LinkedList<>();
            indexQ = new LinkedList<>();
            for(int j = 0; j <docNum; j++){
                priorQ.offer(Integer.parseInt(st.nextToken()));
                indexQ.offer(j);
            }
            print();

2. 문서의 중요도에 따라 출력

• 특정 문서가 출력되는 '순서'를 구하는 문제이므로, 문서가 출력될 때마다 출력된 횟수를 저장 (cnt 변수)
  (1) max 변수에 중요도가 가장 높은 문서의 중요도를 저장해두고, priorQ에서 맨 앞에 있는 요소를 꺼내 max와 같은지 확인한다.
  (2-1) 만약 같다면 해당 문서의 인덱스가 우리가 확인하려는 인덱스와 같은지 확인한다.
  (2-1-1) 같다면 순서(cnt)를 출력하고 break;
  (2-1-2) 찾으려던 문서의 인덱스와 다르다면 그냥 출력하고 넘어간다. (순서는 증가)

(2-2) 만약 다르다면 지금 출력될 순서가 아니므로(중요도 낮음) 다시 큐의 맨 뒤로 넣는다.

    public static void print(){
        int cnt = 1;

        while(!priorQ.isEmpty()) {
            int max = Collections.max(priorQ);
            int cur = priorQ.poll();
            int curIdx = indexQ.poll();

            if(cur == max) {
                if(curIdx == target ) {
                    System.out.println(cnt);
                    break;
                }
                cnt++;
            } else {
                priorQ.offer(cur);
                indexQ.offer(curIdx);
            }
        }
    }

전체 코드

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

public class Main {
    static int t;
    static int docNum;
    static int target;
    static Queue<Integer> priorQ;
    static Queue<Integer> indexQ;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        for(int i = 0; i<t; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            docNum = Integer.parseInt(st.nextToken());
            target = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            priorQ = new LinkedList<>();
            indexQ = new LinkedList<>();
            for(int j = 0; j <docNum; j++){
                priorQ.offer(Integer.parseInt(st.nextToken()));
                indexQ.offer(j);
            }
            print();
        }
    }
    public static void print(){
        int cnt = 1;

        while(!priorQ.isEmpty()) {
            int max = Collections.max(priorQ);
            int cur = priorQ.poll();
            int curIdx = indexQ.poll();

            if(cur == max) {
                if(curIdx == target ) {
                    System.out.println(cnt);
                    break;
                }
                cnt++;
            } else {
                priorQ.offer(cur);
                indexQ.offer(curIdx);
            }
        }
    }
}