[백준] 1966 프린터 큐 - Java

문제 - 프린터 큐

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

1966번: 프린터 큐

 

문제 설명

 

입력

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

 

출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

 

 

예제 입력

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

 

예제 출력

1
2
5

---

접근 방법

 

- 문제를 보면 설명에서 Queue 자료구조에 쌓여서 FIFO 선입 선출 에 따라 인쇄를 한다고 나와 있으니 자료구조 queue를 사용해야 한다는 것을 생각 할수 있다

- queue 에서 제일 앞에 있는 문서의 중요도를 확인하고 

- 이 문서의 중요도 보다 높은 중요도를 가지고 있는 문서가 queue에 있으면 이 문서는 queue의 가장 뒤에 배치한다고 나와 있으니 -> queue에서 빼고 다시 넣어 준는 식으로 풀면 될 것 같다

- 만약 높은 중요도를 문서가 없으면 인쇄를 하는 식으로 반복한다 -> 이럴 때는 그냥 queue에서 빼면 된다

 

- 하지만 이 문제에서 입력 받는것도 다른 문제에 비하면 나름 까다롭다 -> 작성자는 여기에서 계속 이해가 안되었다고 한다....

- 예제 입력을 보면 가장 처음에 테스트 케이스가 몇개인지 나온다 

- 그 후로는 2줄씩 한쌍으로 묶어서 

- 처음에는 문서의 개수와 찾고있는 정수 이렇게 나오고

- 문서의 중요도가 나온다 

- 출력으로는 찾고있는 정수가 몇번째로 인쇄되는지가 출력이다 

---

코드 작성 

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

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

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int testCaseCount = Integer.parseInt(br.readLine());
            StringTokenizer st;

            for (int i = 0; i < testCaseCount; i++) {
                st = new StringTokenizer(br.readLine());
                int N = Integer.parseInt(st.nextToken());
                int M = Integer.parseInt(st.nextToken());
                Queue<Document> queue = new LinkedList<>();

                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    queue.add(new Document(j, Integer.parseInt(st.nextToken())));
                }

                int count = 0;
                while (!queue.isEmpty()) {
                    Document poll = queue.poll();
                    boolean hasHigher = false;

                    for (Document document : queue) {
                        if (document.getImportance() > poll.getImportance()) {
                            hasHigher = true;
                            break;
                        }
                    }

                    if (hasHigher) {
                        queue.add(poll);
                    } else {
                        count++;
                        if (poll.getIndex() == M) {
                            System.out.println(count);
                            break;
                        }
                    }

                }
            }


        }
    }

    static class Document {
        private final int index;
        private final int importance;

        public Document(int index, int importance) {
            this.index = index;
            this.importance = importance;
        }

        public int getIndex() {
            return index;
        }

        public int getImportance() {
            return importance;
        }

    }
}

 

---

 

풀고 느낀점

 

- 이 문제는 제목과 문제 설명 그대로 queue를 이용한 문제이다

- 만약 이 문제에 queue라는 단어가 안나와있으면 자료구조를 어떤걸 사용해야하는지 생각을 좀 했을 것이다

- queue를 얼마나 이해하고 얼마나 사용할수 있는지 확인하는 문제 인 것 같다 

- 자료구조가 많이 중요하다는 것을 느꼈다