[백준] 1966번 : 프린터 큐- JAVA

1966 프린터큐

 

 

해당 문제를 읽자마자 우선순위 큐를 검색해 보았다.

 

우선순위 큐는 힙 구조이고 힙은 완전이진트리의 일종이며 완전이진트리는 마지막 레벨을 제외하고 모든 레벨이 채워져 있는 트리 형태라고 한다.

 

우선순위 큐와 힙 자료구조에 대해서는 나중에 공부를 해야겠다고 넘기고 우선순위 큐의 사용법만 숙지하고 문제를 풀기 시작했다.

 

우선순위 큐는 비교 기준이 필요하고 비교하기 위해 Comparator를 구현해야 했고 나는 문서의 중요도를 내림차순으로 정렬되도록 구현하였다.

(우선순위 큐는 삽입, 제거 시 남은 원소들과 비교하여 반정렬 상태를 유지한다. 자세한 건 나중에 직접 구현해 보면서...)

 

private static class Printer {
    int index;
    int priority;

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

private static class PrinterComparator implements Comparator<Printer> {
    @Override
    public int compare(Printer o1, Printer o2) {
        return Integer.compare(o2.priority, o1.priority);
    }
}

// 우선순위 큐 인스턴스 생성
PriorityQueue<Printer> pq = new PriorityQueue<>(100, new PrinterComparator());

 

 

위와 같이 우선순위 큐를 세팅하고 어떻게 문제를 풀 지 생각을 하는데 우선순위 큐만으로는 중요도가 중복되는 경우 뽑은 Printer 객체의 index와 M을 명확히 비교할 수 없어 한참을 생각했다.

 

결국 Printer 클래스 타입의 큐를 하나 더 추가하여 해결하였다.

 

아래 소스는 Comparator를 별도의 클래스로 만들지 않고 Printer 클래스 내에 구현하였고 우선순위 큐 선언 시 new Printer()를 작성하여 인스턴스를 생성하였다.

 

이게 가능한 이유는 우선순위 큐 생성자 중 1개가 아래와 같기 때문이다.

Comparator<? super E> comparator

 

여기서 Printer(E)의 상위 클래스는 Printer 타입의 Comparator(?)이기 때문에 가능하다(하위 타입 제한).

 

 

 

성공 소스

public class Main {

    private static class Printer implements Comparator<Printer>  {
        int idx;
        int priority;

        // 우선순위 큐 인스턴스 생성 시 Comparator 세팅을 위한 생성자
        public Printer() {}

        public Printer(int idx, int priority) {
            this.idx = idx;
            this.priority = priority;
        }

        @Override
        public int compare(Printer o1, Printer o2) {
            return Integer.compare(o2.priority, o1.priority);
        }
    }

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

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

        while (t-- > 0) {
            PriorityQueue<Printer> pq = new PriorityQueue<>(100, new Printer());
            Queue<Printer> queue = new LinkedList<>();

            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());

            for (int i = 0; i < n; i++) {
                int num = Integer.parseInt(st.nextToken());
                pq.offer(new Printer(i, num));
                
                // queue도 Printer 객체를 삽입한다.
                queue.offer(new Printer(i, num));
            }

            int cnt = 0;

            while (!queue.isEmpty()) {
                // 뽑으려는 우선순위가 queue와 일치하지 않으면 queue 원소를 뒤로 보낸다.
                if (queue.peek().priority != pq.peek().priority) {
                    queue.offer(queue.poll());
                }

                // 뽑으려는 우선순위가 queue와 일치하면 poll
                if (queue.peek().priority == pq.peek().priority) {
                    cnt++;
                    pq.poll();

					// 뽑을 차례의 인덱스와 m이 동일하면 반복문 종료
                    if (queue.poll().idx == m) {
                        sb.append(cnt).append("\n");
                        break;
                    }
                }
            }
        }

        System.out.println(sb);
        br.close();
    }
}

 

 

아이디어를 생각하는 과정에서 너무 좁은 생각에 갇힌 것 같다...