[백준] 1966 문제 - 프린터큐(Java) 문제 해결 방법과 풀이코드

이 문제는 입출력 관계를 이해하기 어려웠다. Queue라는 말을해서 문제푸는 방법의 힌트를 주긴했지만 문제 자체를 이해하기는 쫌 어려웠던것 같다.

 

문제 이해

아래 입력에서 왜 출력 5가 나왔냐면

 

[입력]            ->             [출력]

6 0                                 5

1 1 9 1 1 1

 

입력단계에서 첫번째줄 6은 문서의 개수고 0은 몇번째로 출력되는지 알고싶은 문서의 번호이다. 문서의 번호는 0부터 시작하고 몇번째로 출력되는지는 1부터 시작한다.

 

문서의 개수가 6이므로 문서 배열은 {0, 1, 2, 3, 4, 5} 이렇게 된다. 그리고 중요도의 배열은 {1, 1, 9, 1, 1, 1} 이 된다.

이 둘의 관계를 배열로 묶으면 {{0, 1}, {1, 1}, {2, 9}, {3, 1}, {4, 1}, {5, 1}} 이렇게 되는데

0번째 문서의 중요도는 1이고 자기보다 큰 중요도가 있으므로 뒤로 옮긴다. -> {{1, 1}, {2, 9}, {3, 1}, {4, 1}, {5, 1}, {0, 1}} 

그리고 1번째 문서의 중요도가 또 1이여서 뒤로 옮긴다. -> {{2, 9}, {3, 1}, {4, 1}, {5, 1}, {0, 1}, {1, 1}}

2번째 문서의 중요도는 9여서 출력이되고 나머지 문서의 중요도는 다 똑같아서 순서대로 다 출력이 될것이다. 그래서 5번째로 0번문서가 출력되는 것이다.

 

문제 풀이

{{0, 1}, {1, 1}, {2, 9}, {3, 1}, {4, 1}, {5, 1}} 이 배열 들을 먼저 Queue에 넣는다. 그리고 중요도는 따로 리스트에 담았다. 

Queue가 비어질때 까지 Queue를 한개씩 뽑아서 중요도가 가장 크면 출력 리스트에 담고 중요도 리스트에서 자신의 중요도를 하나 제거한다. 그게 아니면 다시 Queue에 담아서 맨뒤로 오게한다. 

출력리스트에서 몇번째로 출력되는지 알고싶은 문서의 번호를 찾아서 결과에 담고 마지막에 결과를 출력한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//https://www.acmicpc.net/problem/1966
public class 프린터큐_1966 {
    //문서번호, 중요도 배열을 담는 큐
    static Queue<int[]> queue = new LinkedList<>();

    //중요도만 담은 리스트
    static ArrayList<Integer> importanceList = new ArrayList<>();

    //몇번째로 출력되는지 알고싶은 문서의 번호
    static int findDocument;

    //문서가 출력되는 순서
    static ArrayList<int[]> printOrder = new ArrayList<>();

    //출력에 담을 결과
    static StringBuilder result = new StringBuilder();

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

       int testCase = Integer.parseInt(st.nextToken());
       for (int i = 0; i < testCase; i++) {
          st = new StringTokenizer(br.readLine());
          int documentCnt = Integer.parseInt(st.nextToken());
          findDocument = Integer.parseInt(st.nextToken());

          st = new StringTokenizer(br.readLine());
          for (int j = 0; j < documentCnt; j++) {
             int documentImportance = Integer.parseInt(st.nextToken());
             int[] doc = new int[] {j, documentImportance};

             importanceList.add(documentImportance);
             queue.add(doc);
          }

          solve();
          addResult();
          init();
       }

       print();
    }

    private static void solve() {
       while (!queue.isEmpty()) {
          int[] doc = queue.poll();
          int docImportance = doc[1];
          boolean maxImportance = true;

          for (int i = 0; i < importanceList.size(); i++) {
             if (docImportance < importanceList.get(i)) {
                maxImportance = false;
                break;
             }
          }

          if (!maxImportance) {
             queue.add(doc);
          } else {
             for (int i = 0; i < importanceList.size(); i++) {
                if (docImportance == importanceList.get(i)) {
                   importanceList.remove(i);
                   break;
                }
             }

             printOrder.add(doc.clone());
          }
       }
    }

    private static void addResult() {
       for (int i = 1; i <= printOrder.size(); i++) {
          if (printOrder.get(i - 1)[0] == findDocument) {
             result.append(i).append("\n");
             break;
          }
       }
    }

    private static void init() {
       queue.clear();
       importanceList.clear();
       printOrder.clear();
    }

    private static void print() {
       System.out.println(result.toString());
    }
}