[백준] 1966. 프린터 큐 - JAVA

문제

 

 

---

풀이

 

선입선출 구조인 큐를 이용한다.

이때 큐에다가는 배열을 삽입해서 사용해야한다.

Queue<Integer> q = new LinkedList<>();

가 있을때 q안에는 배열의 형태로 넣어줘야한다.

큐에는 {인덱스, 우선순위} 가 두 개 모두 들어가야 하기 때문이다.

그래서 큐에 배열을 넣기 위해서는

q.offer(new Integer[]{인덱스, 우선순위}); 처럼 사용해야 배열의 형태로 넣을수가 있다.

이 점을 활용하여, 앞에서부터 선택정렬을 통해 더 큰 값이 있다면,

맨 뒤로 보내고, 더 큰 값이 없다면,

count값 증가와 함께 큐에서 삭제시켜주었다.

 

---

코드

 

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));

 

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

        for(int i=0; i<tt; i++){

 

            LinkedList<Integer[]> q = new LinkedList<>();

            StringTokenizer st = new StringTokenizer(br.readLine());

            StringTokenizer value = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st.nextToken());

            int M = Integer.parseInt(st.nextToken());

            int count = 0;

 

            for(int k=0; k<N; k++){

                q.offer(new Integer[]{k, Integer.parseInt(value.nextToken())});

            }

            while(!q.isEmpty()){

                //가장 앞에 것을 기준

                Integer[] cur = q.peek();

 

                //큐에 2개 이상 있을 경우

                if(q.size()>1){

                    //뒤에 큰걸 찾기

                    for(int k=1; k<q.size(); k++){

                        //가장 앞 보다 크다면

                        if(cur[1] < (q.get(k)[1])){

                            //찾았다면 그전까지 뒤로 보내기

                            for(int j=0; j<k; j++){

                                q.offer(q.poll());

                            }

                            break;

                        }

                        //cur이 가장 크다면,

                        else if( k== ( q.size()-1 ) &&

                                 cur[1] >= (q.get(k)[1]) ){

                            q.poll();

                            count++;

                            if(cur[0] == M){

                                System.out.println(count);

                            }

                            break;

                        }

                    }    

                }

                //1개 밖에 없는 경우

                else{

                    q.poll();

                    if(cur[0] == M){

                                count++;

                                System.out.println(count);

                            }

                    break;

                }

            }

        }

    }

}