[BOJ] 1966: 프린터 큐(JAVA)

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

1966번: 프린터 큐

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

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 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 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

예제 입력 1 복사

3

1 0

5

4 2

1 2 3 4

6 0

1 1 9 1 1 1

예제 출력 1 복사

1

2

5

 

---

[문제 풀이]

LinkedList에 Int 배열을 넣어줄 것인데, {인덱스, 우선순위} 배열을 넣어줄 것이다.

그리고 우선 순위를 비교해서 가장 앞에 존재하는 즉 첫번째 원소의 우선순위가 큐에 들어있는 모든 원소의 우선순위보다 크다면, count 변수를 증가시키고, 해당 원소를 큐에서 제거하면 된다. 만약 첫번째 원소가 찾던 문서라면 count 변수를 저장하고 반복문을 종료하면 된다. count는 해당 원소를 몇번째로 출력하는지를 저장할 변수이다.

 

그러나 첫번째 원소의 우선순위가 가장 크지 않다면 첫번째 원소부터, 해당 원소보다 우선순위가 큰 원소 중 가장 앞에 있는 원소 전까지의 모든 큐의 원소들을 뒤로 보낸다.

즉, 0번째 원소의 우선순위가 3이고, 1번째 원소의 우선순위는 1, 2번째 원소의 우선순위는 2, 3번째 원소의 우선순위가 4라고 해보자. 그렇다면 0번째 원소의 우선수위보다 큰 원소가 뒤에 존재하고, 그 중 가장 먼저 등장하는 것은 3번째 원소이다. 따라서 0~2번째 원소를 꺼내서 다시 뒤에 넣어준다.

그리고 0번째 원소가 가장 큰 값이 될때까지 반복한다.

 

 

[코드]

import java.util.*;

public class Main {
    public static void main(String[] args) {
    
      Scanner sc = new Scanner(System.in);
      
    
      int T = sc.nextInt();
      StringBuilder sb = new StringBuilder();
      while(T-->0) {
      
           int N = sc.nextInt();
           int M = sc.nextInt();
      
      
           LinkedList<int[]> queue = new LinkedList<>(); //인덱스, 우선순위
           for(int k=0;k<N;k++) {
               queue.offer(new int[] {k, sc.nextInt()});
           }
       
       
           int count=0;
       
           while(!queue.isEmpty()) {
               int[] f = queue.poll(); //가장 첫번째 원소
               boolean isMax = true;
               for(int i=0;i<queue.size();i++) {
                   if(f[1]<queue.get(i)[1]) {
                       queue.offer(f);
                       for(int j=0;j<i;j++) {
                           queue.offer(queue.poll());
                       }
                       isMax=false;
                       break;
                   }
       
               }
            
           if(isMax==false)
               continue;
       
           count++;
           if(f[0]==M)
               break;
    
       
           }
       
           sb.append(count+"\n");
       
       
       
      }
      System.out.print(sb);
     
   }
}