[BOJ] 1966번 - 프린터 스택 (Java)

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

 

이 문제는 사용자에게 문서들의 중요도와 출력 순서를 알고 싶은 특정 문서를 입력 받아, 그 문서가 출력물들 중에서 몇번째로 나올지 알려주는 코드를 짜야했다.

 

중요한 점은 문서열 큐에서 가장 앞에 있는 것을 빼낼 때, 가장 앞의 것의 중요도보다 더 큰 것이 열에 존재한다면 앞의 것을 제일 뒤로 add해야한다는 것이다.

 

코드 1) 출력 순서를 알고 싶은 특정 문서의 위치를 기억하기 위해 큐에 0 삽입

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 {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < testCase; i++) {
            StringTokenizer documents = new StringTokenizer(br.readLine());
            StringTokenizer importance = new StringTokenizer(br.readLine());

            int num = Integer.parseInt(documents.nextToken());
            int test = Integer.parseInt(documents.nextToken());

            Queue<Integer> queue = new LinkedList<>();

            // 큐에 중요도 넣기
            for (int j = 0; j < num; j++) {
                queue.add(Integer.parseInt(importance.nextToken()));

                // test 위치 확인용 0 삽입
                if (j == test)
                    queue.add(0);
            }

            // 출력 순서 확인
            result.append(checkPrintSeq(queue)).append("\n");
        }

        System.out.print(result);
    }

    static String checkPrintSeq (Queue<Integer> q) {
        int max = 1;
        int count = 0;
        int qSize = q.size();

        // 초기 max 중요도 확인
        for (int i = 0; i < qSize; i++) {
            if (q.peek() > max)
                max = q.peek();

            q.add(q.poll());
        }

        while (true) {
            if (q.peek() < max)
                q.add(q.poll());

            // 중요도 max인 요소 만났을 때 빼기
            else {
                q.poll();
                count++; // 빠진 순서

                // 바로 다음이 0이라면 종료
                if (q.peek() == 0)
                    break;

                // 요소가 빠졌다면 중요도 다시 확인
                max = 1;
                qSize = q.size();

                for (int j = 0; j < qSize; j++) {
                    int top = q.poll();

                    if (top > max)
                        max = top;

                    q.add(top);
                }
            }
        }

        return Integer.toString(count);
    }
}

 

 

일단 코드 짜기에 앞서 가장 고민 했던 것은 '어떻게 사용자가 알고자 하는 문서의 위치를 기억하느냐?'였다. 큐에서 poll, add가 반복되면서 특정 문서의 위치도 변화하기 때문이다.

 

그래서 사용한 것이 구별되는 숫자를 그 문서 바로 다음에 넣어 위치를 파악하는 방법이다. 문서의  중요도는 1 이상 9 이하의 정수이므로 이와 구별되는 0을 이용했다.

 

하지만 이보다 더 간단하고 좋은 방법이 있었다!

 

코드 2) Priority Queue 활용하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < testCase; i++) {
            StringTokenizer documents = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(documents.nextToken());
            int M = Integer.parseInt(documents.nextToken());

            StringTokenizer importance = new StringTokenizer(br.readLine());
            Queue<int[]> queue = new LinkedList<>(); // 1차원 배열에 (중요도, 위치) 이렇게 삽입
            // 우선 순위 큐 내림차순으로 (오름차순이 기본 설정)
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder()); // 중요도 순으로 요소 꺼낼 때 활용

            for (int j = 0; j < N; j++) {
                int priority = Integer.parseInt(importance.nextToken());
                queue.add(new int[]{priority, j});
                priorityQueue.add(priority);
            }

            int count = 0;
            while (!queue.isEmpty()) {
                int[] current = queue.poll();
                if(current[0] == priorityQueue.peek()){
                    count++;
                    priorityQueue.poll();

                    if (current[1] == M) {
                        result.append(count).append("\n");
                        break;
                    }
                }

                else {
                    queue.add(current);
                }
            }
        }

        System.out.print(result);
    }
}

 

일반적으로 큐에서 요소를 꺼내거나 확인할 때 (poll, peek) 가장 앞의 요소가 반환된다. 하지만 Priority Queue, 우선 순위 큐는 큐의 요소를 꺼낼 때 가장 우선 순위가 높은(가장 작거나 큰, 기본은 오름차) 요소를 꺼낸다.

 

그럼 이 우선순위 큐를 어떻게 이용한다는 걸까?

 

일단 기본 큐 요소를 1차원 배열로 하여, 입력 받은 문서의 중요도와 큐에서의 처음 위치를 함께 넣는다. 그리고 Priority Queue에는 중요도만 넣는다.

 

앞서 문제 설명에서 큐에서 요소를 하나씩 출력하려 할 때 뒷 요소들 중 중요도가 더 큰 것이 있다면 그 요소(제일 앞 요소)를 가장 뒤로 보낸다고 했다. 이 말은 즉슨 결국에 문서를 중요도가 큰 순으로 출력하겠다는 것이므로, 큐에서 꺼낸 문서의 중요도와 PriorityQueue에서 peek를 한 값(중요도)이 같다면 출력하면 되는 것이다.

 

특정 문서가 몇 번째로 출력되는지 계산하기 위해서는 count 값을 문서가 빠져나갈 때마다 증가시켜주고, 문서의 기존 순서 값이 원래 찾으려던 문서의 순서 값과 같다면 반복문을 멈춘다.

 

Priority Queue

삽입되는 순서와 상관 없이 큐 요소를 우선 순위가 높은 순으로 삭제시켜 주는 자료구조이다.
Priority Queue는 기본적으로 삭제 시 오름차순으로 요소를 꺼낸다.

만약, 내림차순으로 이용 시 Collections.reverseOrder()를 사용한다. (이는 Comparator의 일종)

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

---

 

항상 큐에서 특정 요소의 위치를 어떻게 기억하나 싶었는데, 오늘 문제와 같이 기존 순서를 따로 또 저장해주는 방법을 활용할 수 있겠다 생각했다. 또한 Priority Queue를 처음 접했는데, 우선순위에 따라 가장 먼저 요소를 꺼내야한다는 조건 등이 있을 때 사용하도록 잘 익혀놔야겠다.