[210916] 백준 1966번 문제 풀이 / 프린터 큐

 

 

문제의 핵心

1. 데이터의 개수(N <=100) 가 많지 않으므로, 단순히 문제에서 요구하는 대로 구현한다.
2. 현재 리스트에서 가장 큰 수가 앞에 올 때까지 회전시킨 뒤에 추출한다.
3. 가장 큰 수가 M이면서 가장 앞에 있을 때 프로그램을 종료한다.

 

 

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

public class Q4_1966 {

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

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

         while(T --> 0) {
               StringTokenizer st = new StringTokenizer(br.readLine());
    
               int N = Integer.parseInt(st.nextToken());
               int M = Integer.parseInt(st.nextToken());

               LinkedList<int[]> q = new LinkedList<>();
               st = new StringTokenizer(br.readLine());

              for(int i=0; i<N; i++) {
                  q.offer(new int[] {i, Integer.parseInt(st.nextToken())});  // 초기위치, 중요도
              }

              int count = 0; 

              while(!q.isEmpty()) {
                    int[] front = q.poll(); 
                   // 원소의 초기 위치(인덱스)와 중요도를 q에서 꺼내어 차례로 0과 1 인덱스에 담기
                     boolean isMax = true;

                     for(int i=0; i<q.size(); i++) {
                         if(front[1] < q.get(i)[1]) { //처음 뽑은 원소의 중요도 < i번째 원소의 중요도
                             q.offer(front); // 중요도가 더 큰 원소가 있다면 현재 front원소를 다시 q 끝에 담기

                              for(int j=0; j<i; j++) { // i가 도달한 곳(중요도가 더 큰 원소가 있는 곳) 까지 그 앞 원소들도 꺼내어 다시 끝에 담기
                                 q.offer(q.poll());
                              }

                             isMax = false;
                             break;
                          }
                     } // outer for 문의 끝

                    // front 원소가 가장 큰 원소가 아니었으므로 q가 비어있지 않은 한, 다른 반복문으로
                    if(isMax == false) {
                           continue;
                      }

                     // front 원소가 가장 큰 원소였으므로 해당 원소는 출력해야하는 문서다. 
                     count++;
                     if(front[0] == M) { // 원소의 초기 위치와 입력받은 원하는 원소 인덱스
                          break;
                      }
               } //inner while 의 끝
      
              sb.append(count).append('\n');
 
         } //outer while 의 끝
         System.out.println(sb);


     }

}