[백준] 1966 - 프린터 큐 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

---

링크

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

1966번: 프린터 큐

문제

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

현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 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 구조를 이용해서 풀이를 요구한다.  문제의 출력 조건에 따라 데이터를 큐에서 잘 이용할 수 있는지 묻는 문제다. 이 정도 인지하고 풀이로 들어가자.

풀이

 문제에서 고려해볼 점은 두 가지 정도 되는 것 같다. 

 

1. 중요도가 같은 문서에 대한 처리
2. 출력 형태

 

 1번 이슈는 큐를 사용하면서 해결이 가능하다. 문제에서 제시한 입력 케이스 중 3번째 케이스는 큐에 들어간 대로 중요도를 판단하고 출력함을 나타내고 있다.

 

 2번 이슈 같은 경우에는 개인적으로 내가 골치로 여겼다. 문제 입력에서 준 것은 중요도를 출력할 문서의 인덱스 번호이다. 이 인덱스 번호의 중요도가 우리가  출력해야 하는 데이터다. 개인적으로 이 부분을 제대로 정리하지 않아서 나중에 출력할 때, 굉장히 혼동되었는데, 항상 본인이 출력할 데이터 형태에 대해 확실한 명시를 하고 풀이에 임해야 한다.

 

 특히, 이 문제의 경우, 나는 int [] 배열 형태의 LinkedList를 사용하였다. 이유는 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 {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer stk;

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

        for (int i = 0; i < tc; i++) {
            // 문서 갯수, 목적 인덱스
            stk = new StringTokenizer(br.readLine(), " ");

            int cnt = Integer.parseInt(stk.nextToken());
            int target_idx = Integer.parseInt(stk.nextToken());

            int[] datas = new int[cnt];

            //각 문서의 중요도
            stk = new StringTokenizer(br.readLine(), " ");

            for (int k = 0; k < cnt; k++) {
                datas[k] = Integer.parseInt(stk.nextToken());
            }

            sb.append(solution(datas, target_idx))
                    .append("\n");
            
        }
        
        
        System.out.println(sb);

    }


    public int solution(int[] datas, int target_idx) {
        //사본을 통해 중요도 순서 용도로 사용
        int[] datas_sorted = datas.clone();
        int sorted_idx = datas_sorted.length - 1;
        int order = 0;
		//중요도 순으로 출력하기 위한 정렬
        Arrays.sort(datas_sorted);
        // [0] - Value, [1] - IDX
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < datas.length; i++) {
            queue.add(new int[]{datas[i], i});
        }
        
        while (!queue.isEmpty()) {
            
            //출력할 문서는 문서의 중요도(Value)로 판단
            if (queue.peek()[0] < datas_sorted[sorted_idx]) {
                queue.add(queue.poll());
            } else {
                //출력할 문서를 찾았다면
                order += 1;
                
                //해당 문서의 인덱스와 요구하는 인덱스 확인
                int[] tmp = queue.poll();
                if (tmp[1] == target_idx) {
                    break;
                }
                sorted_idx--;

            }

        }


        return order;
    }
    
}

결과

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.