[Baekjoon] 1966 - 프린터 큐

📝 문제

 

 

🔑 풀이 과정

이 문제를 처음 봤을때는 우선순위라는 말이 나오길래 PriorityQueue 클래스를 써야 하나 어쩌나 고민했는데,

그냥 기본적인 큐를 가지고 문제를 그대로 구현시키면 된다!

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

이 조건들을 구현시키기만 하면 된다.

 

그리고 우리는 이런 프린터가 있을 때 어떤 한 문서가 몇 번째로 인쇄되는지를 알아내야 한다.

그 한 문서를 구분하는 법은, 그 문서가 처음 입력 받을 때 몇 번째로 입력받는지 번호를 줘서 구분할 것이다.

그래서 Queue를 사용할때, 단순히 int형으로 우선순위만 넣는게 아니고 int형 배열을 넣어서 입력받은 순서, 중요도 두 가지를 넣어줄 것이다.

 

1번 조건은 Queue의 맨 앞의 문서를 꺼내는 걸로 구현(poll or remove). Queue는 맨 앞의 문서를 제거한 상태로 남아있다.

2번 조건은 다음과 같이 구현한다.

현재 출력 순서를 가지고 있는 변수를 선언한다.

for문을 사용해서 남아있는 문서들의 중요도를 검사한다.

1) 만약 중요도가 높은 문서가 존재한다.

→ 현재 꺼낸 문서 출력 불가능

→ 현재 문서를 Queue의 맨 뒤에 재배치(add or offer)

2) 만약 중요도가 높은 문서가 존재하지 않는다.

→ 현재 꺼낸 문서 출력 가능

→ 현재 꺼낸 문서와 입력받은 M이 같으면 우리가 원하는 것이 구해졌으므로 현재의 순서를 출력하고 반복문 탈출

→ 현재 꺼낸 문서와 입력받은 M이 다르면 순서를 증가시키고, 맨 앞의 원소를 다시 꺼내고 검사하고 이것을 반복한다.

 

[예제 입력의 2번째 테스트 케이스로 설명]

 

🔓 답안

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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));
        StringTokenizer st;

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

        //테스트 케이스 수 만큼 반복문 진행
        for(int i = 0; i < T; i++){
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); //문서의 개수
            int M = Integer.parseInt(st.nextToken()); //순서가 궁금한 문서의 위치

            Queue<int[]> queue = new LinkedList<>();
            //N개의 문서 중요도 입력 받기
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                queue.add(new int[]{j, Integer.parseInt(st.nextToken())});
            }

            int count = 1; //현재 프린터 출력 순서
            while(true){
                int[] item = queue.poll(); //현재 문서

                boolean flag = true; //출력 가능한지 상태

                for(int[] q : queue){
                    if(q[1] > item[1]){ //나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 있을 때
                        flag = false;
                        break;
                    }
                }

                if(flag){
                    if(item[0] == M){
                        bw.write(count + "\n");
                        break;
                    }
                    else
                        count++;
                } else{
                    queue.offer(item);
                }
            }
        }

        bw.flush();
        bw.close();
    }

}

 

 

 

🖤 알고리즘 분류

- 구현

- 자료 구조

- 시뮬레이션

- 큐