[백준/JAVA] 1966번 : 프린터 큐

문제

Queue 자료구조를 이용해서 요구사항을 구현만 하면 되는 문제이다.

 

유의할 점은 중요도가 같은 경우가 있을 수 있기 때문에, 각각 문서의 번호와 값을 함께 저장해주어야 한다.

---

풀이

우선 Queue에 각 테스트케이스의 두 번째 줄에 있는 문서 정보를 입력받는다.

문서 정보는 2개의 인덱스를 가진 int배열로 0번 인덱스에는 문서 번호를, 1번 인덱스에는 중요도 값을 넣을 것이다.

이 문서정보를 순서대로 Queue에 넣어준다.

Queue<int[]> queue = new LinkedList<>();

for(int i=0;i<n;i++){
    //[0] : 번호 , [1] : 값
   int[] arr = {i,Integer.parseInt(st.nextToken())};
   queue.add(arr);
}

---

이제 queue에서 값을 하나씩 꺼낸다. -> queue.peek()

꺼낸 값과 queue에 남아있는 모든 값을 비교하여 꺼낸 값보다 큰 값이 하나라도 있는지 확인한다.

1. 꺼낸 값보다 큰 값이 있는경우 값을 꺼내서 다시 queue에 넣어준다.

   -> queue.poll() -> queue.add()

2. 꺼낸 값보다 큰 값이 하나도 없는 경우 값을 꺼내고, 몇 번째로 꺼냈는지 기록한다.

   -> 몇번째로 꺼냈는지를 의미하는 order 변수를 1로 초기화 하고, 하나 꺼낼 때마다 ++ 해준다.

3. 만약 2번에서 꺼낸 값이 번호가 구하고자하는구하고자 하는 번호와 일치한다면 그때의 order변수의 값이 구하고자 하는 값이다.

---

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        int cases = Integer.parseInt(br.readLine());
        for(int i=0;i<cases;i++){
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());//문서의 개수
            int m = Integer.parseInt(st.nextToken());//몇번째에 놓여있는지
            String str = br.readLine();
            int result  = findOrder(n, m, str);
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
    
    static int findOrder(int n, int m, String str){
        StringTokenizer st = new StringTokenizer(str);
        Queue<int[]> queue = new LinkedList<>();
        int order=1;
        for(int i=0;i<n;i++){
            //[0] : 번호 , [1] : 값
           int[] arr = {i,Integer.parseInt(st.nextToken())};
           queue.add(arr);
        }

        while(true){
            int[] peekArr = queue.peek();
            boolean ok = true;
            
            //전부다 돌면서 peekArr보다 큰 값이 있나 확인
            for (int[] arr : queue) {
               //peekArr보다 큰 값을 찾았을경우 꺼내서 맨 뒤로 보내고 for문을 종료한다.
                if(peekArr[1]<arr[1]){
                    int[] pollAndAdd = queue.poll();
                    queue.add(pollAndAdd);
                    ok = false;
                    break;
                }
            }
            //나보다 큰 값이 있었으면 ok = false
            //나보다 큰 값이 없었으면 ok = true -> poll 하면 된다.
          
           if(ok && peekArr[0]==m){//이번 값이 출력 가능하고, 찾고자 하는 번호랑 같으면 order를 반환한다.
                return order;
            }else if(ok && peekArr[0]!=m){//이번 값이 출력 가능하지만, 찾고자하는 번호가 아니면 poll()만 한다.
                int[] pollAndAdd = queue.poll();
                order++;
            }
        }
    }
}