[백준] 프린터 큐 JAVA

728x90

반응형

[백준] 프린터 큐

---

접근

• 우선순위 큐
• 정렬
• 큐

---

풀이

강의를 안들을 때 틈틈이 백준에서 문제를 풀고 있다. 이제 class 2의 문제를 거의 다 풀었는데 실버 3 티어가 되었다. 실버 내의 저 티어 문제들은 그래도 아직 깊은 생각 없이 바로바로 풀리는 거 같다.

 

오늘의 문제의 제목은 프린터 큐이다. 제목부터 큐를 사용하라고 나와있다. 중요도가 있고 중요도순으로 출력을 할 경우 원하는 문서가 몇 번째에 나오냐 라는 문제인데 우선순위 큐 한 번 써봐라 하는 문제 같았다. 그렇게 우선순위큐로 제출하자마자 실패가 떴다. 문제를 자세히 보니 주어지는 값은 중요도이고 중요도는 같지만 문서 자체는 다른 것을 고려하지 않았다. 중요도가 낮은 출력물은 맨 뒤에 넣어지게 되고 우선순위 큐만 사용해서는 원하는 출력을 얻을 수가 없었다.

 

그럼 리스트를 사용해서 중요도를 체크하고 아니면 다시 맨뒤로 넣어주고 해야 하나 생각하던 중 그냥 일반 큐를 쓰면 해결되는 문제라는 걸 깨달았다.  다시 맨 뒤로 들어가 순서를 기다린다는 것은 선입선출 구조를 가진 큐였고 우선순위에 대한 것만 객체나 배열을 통해 따로 체크해 주면 될 것 같았다.

public static class Document {
        int index;
        int priority;

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

문서를 관리할 클래스이다. 큐에 들어갈 객체로 문서의 인덱스 값과 중요도를 가지고 있다.

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

for (int i = 0; i < t; i++) {
    String[] nAndTarget = br.readLine().split(" ");
    int n = Integer.parseInt(nAndTarget[0]);
    int target = Integer.parseInt(nAndTarget[1]);

입력을 받는 부분이다.

  Queue<Document> que = new LinkedList<>();
  String[] line = br.readLine().split(" ");

  for (int j = 0; j < n; j++) {
     int priority = Integer.parseInt(line[j]);
     que.offer(new Document(j, priority));
  }

사용할 큐를 선언하고 문서의 인덱스 값과 중요도를 가진 객체를 큐에 추가해준다.

  int count = 0;
  while (!que.isEmpty()) {
     Document current = que.poll();
     boolean flag = false;

문서의 출력 순서를 세어줄 count 변수를 선언한다. 순서대로 앞에서 부터 큐에 들어있는 객체를 꺼내 체크한다.

   for (Document doc : que) {
      if (doc.priority > current.priority) {
         flag = true;
         break;
      }
   }

남은 큐를 선회하며 현재 꺼낸 문서의 중요도와 비교한다.

   if (flag) {
      que.offer(current);
   } else {
      count++;
      if (current.index == target) {
         bw.write(count + "\n");
         break;
      }
   }

만약 flag가 true라면 현재 문서보다 큐에 중요도가 더 높은 문서가 존재하기 때문에 다시 맨 뒤에 넣어준다. flag가 false라면 큐에 현재 문서보다 중요도가 높은 문서가 존재하지 않기 때문에 문서를 카운트를 증가하고, 만약 출력한 문서가 목표 문서라면 종료한다.

---

전체 코드

import java.util.*;
import java.io.*;

public class Main {
    public static class Document {
        int index;
        int priority;

        public Document(int index, int priority) {
            this.index = index;
            this.priority = priority;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        for (int i = 0; i < t; i++) {
            String[] nAndTarget = br.readLine().split(" ");
            int n = Integer.parseInt(nAndTarget[0]);
            int target = Integer.parseInt(nAndTarget[1]);

            Queue<Document> que = new LinkedList<>();
            String[] line = br.readLine().split(" ");

            for (int j = 0; j < n; j++) {
                int priority = Integer.parseInt(line[j]);
                que.offer(new Document(j, priority));
            }

            int count = 0;
            while (!que.isEmpty()) {
                Document current = que.poll();
                boolean flag = false;

                for (Document doc : que) {
                    if (doc.priority > current.priority) {
                        flag = true;
                        break;
                    }
                }

                if (flag) {
                    que.offer(current);
                } else {
                    count++;
                    if (current.index == target) {
                        bw.write(count + "\n");
                        break;
                    }
                }
            }

        }

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