[백준] 1966번 프린터 큐(Java)

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

1966번: 프린터 큐

 

인쇄하고자 하는 문서의 중요도가 주어지고 뒤에 더 중요한 문서가 존재한다면 앞의 문서를 다시 큐에 넣는 문제이다.

이때 특정 문서의 출력되는 순서를 알고자 하므로 문서는 중요도와 처음 순서 정보를 가지고 있어야 한다.

또한 큐의 최대값을 찾을 수 있어야 한다.

 

큐에 두 가지 정보를 저장하는 방법으로 두 가지를 생각할 수 있다.

1. 커스텀한 클래스를 사용

2. int 배열을 사용

 

처음 생각한 방법은 중요도와 초기 위치를 저장하는 것이 아니라 int인 중요도와 boolean인 목표 여부를 저장하는 것이어서 새로 클래스를 만들어 사용하였다.

    static class Element {
        int value;
        boolean isTarget = false;
    }
    
    static Queue<Element> queue;

 

 

그리고 출력할 문서 뒤에 더 중요한 문서가 있는지 찾는 방법으로 크게 3가지 방법을 생각하였다.

1. Collections.max(queue);

2. Queue가 아닌 LinkedList로 사용하여 get() 메소드를 통한 순회

3. enforced for문을 통한 순회

4. 큐를 복사하여 요소를 뽑아서 순회

 

Element라는 커스텀한 클래스를 사용하였을 때는 1번 방법을 사용할 수 없었다.

또한 해당 문제에서는 최대값을 찾는 것이 목적이 아니라 뒤에 더 중요한 문서가 있는지 찾는 것이 중요하기 때문에 3번 방법을 사용하였다.

    public static boolean checkImportance() {
        int first = -1;
        for(Element e : queue) {
            if (first == -1) {
                first = e.value;
            }
            else if (first < e.value) {
                return false;
            }
        }
        return true;
    }

 

전체 코드

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

public class Main {

    static class Element {
        int value;
        boolean isTarget = false;
    }

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static int N;

    static Queue<Element> queue;

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

        N = stoi(st.nextToken());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int total = stoi(st.nextToken());
            int target = stoi(st.nextToken());
            int answer = 1;

            st = new StringTokenizer(br.readLine());
            queue = new LinkedList<>();
            for (int j = 0; j < total; j++) {
                Element element = new Element();
                if(j == target) element.isTarget = true;
                element.value = stoi(st.nextToken());
                queue.add(element);
            }

            while(!queue.isEmpty()){
                if(!checkImportance()){
                    queue.add(queue.poll());
                }
                else {
                    Element element = queue.poll();
                    if(element.isTarget){
                        System.out.println(answer);
                        break;
                    }
                    else answer++;
                }
            }
        }
    }

    public static boolean checkImportance() {
            int first = -1;
            for(int[] p : queue) {
                if (first == -1) {
                    first = p[0];
                }
                else if (first < p[0]) {
                    return false;
                }
            }
            return true;
        }
}

 

그리고 클래스를 사용하지 않고 int 배열에 중요도와 초기 위치를 저장하는 방법을 통해 풀어보았다.

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

public class Main {

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static int N;

    static Queue<int[]> queue;

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

        N = stoi(st.nextToken());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int total = stoi(st.nextToken());
            int target = stoi(st.nextToken());
            int answer = 1;

            st = new StringTokenizer(br.readLine());
            queue = new LinkedList<>();
            for (int j = 0; j < total; j++) {
                queue.add(new int[] {stoi(st.nextToken()), j});
            }

            while(!queue.isEmpty()){
                if(!checkImportance()){
                    queue.add(queue.poll());
                }
                else {
                    int[] paper = queue.poll();
                    if(paper[1] == target){
                        System.out.println(answer);
                        break;
                    }
                    else answer++;
                }
            }
        }
    }

    public static boolean checkImportance() {
        int first = -1;
        for(int[] p : queue) {
            if (first == -1) {
                first = p[0];
            }
            else if (first < p[0]) {
                return false;
            }
        }
        return true;
    }
}