[BOJ 1966] 프린터 큐 - JAVA

오느른.... 구현 문제... 프린터 큐를 풀어보았습니다.

구현 문제는 많이 풀지 않아서 그런지.. 알고리즘을 생각하는게 쉽지 않구녕..........

그래서....... 도움을 받아서 풀었습니다.........호호.........

 

구현 내용

어휴.. 문제도 길어요... 

문제 해석 하는거 부터가 쉽지 않았습니다..........

(맨날 그런거 같기도..)

 

구현방법

가장 중요한 것은 가장 큰 값의 위치를 파악하는 포인터 하나.

찾아야할 값에 큐에서의 위치를 파악하는 포인터 하나 이렇게 두 개의 포인터를 준비해야한다는 것입니다!

 

가장 큰 값은 리스트를 정렬하여서 찾으시면 됩니다!

 

자세한 내용은 주석을 통해 알려드리도록 하겠습니다.

↓↓↓↓↓↓↓↓↓↓↓↓    ↓↓↓↓↓↓↓↓↓↓↓↓↓↓    ↓↓↓↓↓↓↓↓↓↓↓↓↓

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;


public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 입력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 출력

        StringTokenizer stok;
        int n = Integer.parseInt(br.readLine());    //테스트케이스 개수
        Queue<Integer> q = new LinkedList<>();      //FIFO에 사용될 큐
        ArrayList<Integer> list = new ArrayList<>();//최대값을 찾기위한 리스트

        for(int i=0;i<n;i++) {
            stok = new StringTokenizer(br.readLine());
            int repeat = Integer.parseInt(stok.nextToken());    //데이터 개수
            int point = Integer.parseInt(stok.nextToken());     //찾아야될 데이터 위치
            int maxPoint = 0;     //ArrayList에서 최대값 위치
            stok = new StringTokenizer(br.readLine());
            for (int j = 0; j < repeat; j++) {      //큐와 리스트에 데이터 넣기
                int data = Integer.parseInt(stok.nextToken());
                q.offer(data);
                list.add(data);
            }
            Collections.sort(list);     //리스트를 정렬하여 가장 큰 값 찾기
            maxPoint = list.size()-1;   //리스트에 가장 마지막에 있는값  == 가장 큰 값
            int count = 0;              //결과 값
            while(true){
                int tmp = q.poll();     //q에서 이번에 나오는 값
                if(tmp == list.get(maxPoint)){//현재 값이 최대값과 같으면
                    count++;        //데이터를 뽑는다
                    if(point==0)    //종료
                        break;
                    maxPoint--;     //리스트에서 앞으로 포인터 당기기
                }
                else{
                    q.offer(tmp);   //가장 큰 값이 아니면 큐에 다시 넣기
                    if(point==0){   //뽑아야할 데이터 위치가 가장 앞이라면
                        point = q.size();   //가장 마지막 위치로 옮기기
                    }
                }
                point--;        //찾아야할 데이터 위치 앞으로 당기기
            }
            bw.write(String.valueOf(count)+"\n");
            //테스트 케이스 끝날 때 마다 q와 리스트 초기화화            q.clear();
            list.clear();
        }

        bw.flush();
    }
}