프린터 큐(1966)

프린터 큐(1966)

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

public class Main{
  public static void main(String[] args) throws IOException {
      
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int t = Integer.parseInt(br.readLine()); // 테스트 케이스
    
    for(int i = 0; i < t; i++){
        
      StringTokenizer st = new StringTokenizer(br.readLine());
      
      int n = Integer.parseInt(st.nextToken()); // 문서의 개수
      int m = Integer.parseInt(st.nextToken()); // 궁금한 문서 , 추적용
      
      Queue<Integer> que = new LinkedList<>();
      int[] arr = new int[n]; // 가장 큰 우선순위를 위한 배열
      
      int cnt = 0;
      
      st = new StringTokenizer(br.readLine());
      int index = 0;
      while(st.hasMoreTokens()){
        int num = Integer.parseInt(st.nextToken());
        que.add(num);
        arr[index] = num;
        index++;
      }
      
      Arrays.sort(arr);
      
      boolean flag = false; // for문을 빠져나오기 위한 조건
      
      for(int j = n-1; j >= 0; j--){
        while(true){
          if(que.peek() == arr[j] && m == 0){ 
          // que의 가장 앞 == 현재 우선순위 && 궁금한 문서의 위치 (0이면 맨앞, 1이면 두번째..)
            cnt++;
            flag = true;
            break;
          }
          
          m = (m != 0)? --m : que.size() - 1; 
          // que의 앞 문서가 제거가 되든, 아니면 문서의 위치가 바뀌든 m은 줄어든다
          
          if(que.peek() == arr[j]){
            que.poll();
            cnt++;
            break;
          } else {
            int temp = que.poll();
            que.add(temp);
          }
        }
        
        if(flag) break;
          
      }
      
      sb.append(cnt + "\n");
        
    }
    
    bw.write(sb + "");
    bw.flush();
    bw.close();
    br.close();
  }
}

풀이과정

1) 우선순위 문서를 어떻게 찾아낼까 하다가 그냥 배열에 넣고 역순으로 조회하는걸 택하였다.
2) 그 후 고민했던 부분은 타겟문서를 어떻게 추적할 것인가였다.
3) 타겟문서의 위치는 줄어들다가 0 이후에는 제일 뒤로 이동하는 타겟문서의 추적 알고리즘을 구현하였다.
4) 그리고 조건에 따라 que.peek()이 제거 되거나 뒤로 이동시키는 알고리즘을 구현하였다.
5) que의 제일 앞에 있는 문서와 우선순위 문서가 같고, 타겟문서가 제일앞(m ==0)이면 타겟문서가 출력되기 때문에 cnt++를 후 while에서 나오도록 하였다.
6) m == 0 일 때가 필요한 이유는 문서들이 동일한 우선순위를 가질 수 있기 때문이다.
7) 처음에는 원하는 값이 나오지 않았다. 로직을 뜯어보니, while에서는 나오더라도 for문에서는 빠져나오지 않았기 때문에 다시 while로 들어가 cnt++ 되는 상황이 발생하였다.
8) for문을 빠져나올 수 있는 변수를 추가하여 해결하였다.

• 성공
• 메모리 : 16404 KB
• 시간 : 164 ms