[백준] 1966 프린터 큐

www.acmicpc.net/problem/1966

1966번: 프린터 큐

2020-11-24

---

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main1966 {
    public static int N, M, answer;
    public static Integer arr[];
    public static Queue<int[]> q;
    
    public static void solve() {
        int idx = 0;
        
        loop:while(!q.isEmpty()) {
            int tmp[] = q.poll();
            int x = tmp[0];
            int y = tmp[1];
            if(arr[idx] == y) {
                idx++;
                if(x == M) {
                    answer = idx;
                    break loop;
                }
            } else {
                q.add(new int[] {x, y});
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int test = sc.nextInt();
        for(int ts = 1; ts <= test; ts++) {
            answer = 0;
            N = sc.nextInt();
            M = sc.nextInt();
            if(N == 1 && M == 0) {
                answer = 1;
                int x = sc.nextInt();
            }
            else {
                q = new LinkedList<int[]>();
                arr = new Integer[N];
                for(int i = 0; i < N; i++) {
                    int x = sc.nextInt();
                    arr[i] = x;
                    q.add(new int[] {i, x});
                }
                Arrays.sort(arr, Collections.reverseOrder());
                solve();
            }
            System.out.println(answer);
        }
    }
}
 

 

1. Queue의 문서의 갯수가 1이 아닌 경우, N만큼 문서의 중요도를 입력 받는다. 이 때, 1차원 배열에 중요드를 받고, queue에는 순서를 나타내는 값과 중요도를 같이 받았다.

 

2. 중요도를 받은 1차원 배열을 중요도가 높은 순부터 내림차순으로 정렬하였다. Queue에 있는 문서들을 매칭 했을 때, 가장 높은 문서의 중요도부터 차례대로 찾기 위해서이다.

 

3. queue에 있는 문서를 하나씩 빼면서, 현재 array에 있는 문서의 중요도와 같은 경우 (즉, 제일 큰 경우), 현재 가장 중요도가 높은 문서를 가리키는 idx값을 +1 해주고, 만약 현재의 문서가 찾는 문서인 경우 함수를 끝낸다.

 

만약, 현재 문서의 중요도가 가장 높지 않은 경우, 다시 queue에 넣어서 반복한다.