[BaekJoon] 1966 프린터 큐 JAVA

🔗 백준 1966 프린터 큐 https://www.acmicpc.net/problem/1966

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

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

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

---

입력

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

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

---

출력

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

---

풀이

이 문제는 Queue를 구현해야했던 문제이다.

입력 들어온 N개의 문서가 큐 안에 나열되어있고, 그 중 중요도가 높은 문서부터 차례대로 poll() 해야했다.

즉, 각 문서와 문서의 중요도를 갖고있어야한다는 것이다.

나는 이를 저장하기 위해 static member class를 생성하여줬다.

Inner class 와 static member class

Inner class를 new 연산자를 사용하여 두개의 새로운 인스턴스를 만들게 되면 다른 참조를 갖은 두개의 객체를 생성하게 된다.

static member class로도 두번 객체를 생성하게 되면 static이 붙었다고 해서 같은 참조를 갖는 객체가 생성되지 않는다.

즉, 클래스에 static 키워드가 붙게 된다면 인스턴스 생성 방식이 변화할 뿐, 클래스가 인스턴스의 역할을 하는것은 아니다라는 의미이다.

Inner Class

1. new 연산자를 두번 사용하여 두개의 인스턴스 생성 시 다른 참조를 갖은 두개의 객체를 생성

2. 외부 클래스의 인스턴스가 존재해야만 만들 수 있다.

   • Inner class는 외부 클래스에 대한 숨은 외부 참조를 갖게된다.

static member class

1. new 연산자를 한번 사용하여 두개의 인스턴스 생성 시 다른 참조를 갖은 두개의 객체를 생성
   • 클래스에 static 키워드가 붙게된다면 인스턴스 생성 방식이 변화할 뿐, 클래스가 인스턴스의 역할을 하는것은 아니다.
2. 외부 인스턴스가 없어도 만들 수 있다.
   • 외부 참조가 존재하지 않는다.

외부 참조의 단점

1. 참조값을 담아야하기 때문에, 인스턴스 생성 시 시간

   공간적 성능 저하

2. 외부 인스턴스에 대한 참조로 인해 가비지 컬렉터가 인스턴스를 수거하지 못해 메모리 낭비 발생

즉, 내부 클래스 선언 시에는 static member class로 생성하는 편이 이점이 더 많다.

참고 블로그 https://siyoon210.tistory.com/141

그리고 문서의 중요도만 갖는 PriorityQueue도 따로 선언하여줬다.

PriorityQueue (우선순위 큐)

PriorityQueue

일반적인 큐의 구조인 FIFO를 갖지만, 데이터가 들어온 순서대로 나가는 것이 아니라 우선순위를 결정하고, 그 우선순위가 높은 데이터가 먼저 나가는 구조이다.

PriorityQueue 특징

1. 우선순위가 높은 요소를 먼저 꺼내어 처리한다.

2. 내부 요소는 Heap으로 구성되어 이진트리의 구조이다.

3. 내부 요소가 Heap으로 구성되어 시간 복잡도가 O(nLogn)이다.

참고 블로그 https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

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

public class Main {
    static class Papers{
        int paper, priority;

        public Papers(int paper, int priority) {
            this.paper = paper;
            this.priority = priority;
        }
    }

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

        Queue<Papers> q = new LinkedList<>();
        
        // 우선순위가 높은 순으로 정렬해야하므로 reverseOrder를 통해 역정렬을 해준다.
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

        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());

            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                int priority = Integer.parseInt(st.nextToken());
                q.add(new Papers(j,priority));
                pq.add(priority);
            }

            int count = 1; // 몇번째인지 카운트
            while(true) {
                // 큐의 첫 원소의 중요도와 우선순위큐의 제일 높은 중요도가 일치하면
                if(Objects.requireNonNull(q.peek()).priority == Objects.requireNonNull(pq.peek())) {
                    // 목표한 원소라면 반복문을 멈춘다
                    if(q.peek().paper == m) break;
                    // 아니라면 카운트를 올려주고
                    count++;
                    // 큐와 우선순위 큐에서 해당 문서, 해당 중요도를 빼준다
                    q.poll();
                    pq.poll();
                    
                // 큐의 첫 원소 중요도와 우선순위 큐의 제일 높은 중요도가 일치하지않다면 해당 문서를 큐의 맨 뒤로 보내준다
                } else q.add(q.poll());
            }
            q.clear();
            pq.clear();
            sb.append(count).append("\n");
        }
        System.out.println(sb);
    }
}