[Java] 백준 1966. 프린터 큐

정석·2024년 5월 10일

Java

알고리즘 학습

목록 보기

33/67

🧑🏻‍💻문제

💡문제 분석 요약

각 테스트 케이스별 우선순위에 대한 수를 입력받는다.
해당 우선순위별로 프린트가 출력되는데 우선순위가 높은 게 먼저 출력된다.
우선순위가 낮은 경우 다시 뒤로 순번이 밀리게 된다.

💡알고리즘 설계

일단 우선순위로 인해 제일 높은 수인 경우 먼저 출력되므로, 최대값을 구하고자 하였다.
해당 최대값으로 프린트 로직이 구현되는데, 입력받은 M의 값과 프린트 출력된 값의 인덱스와 같다면 값을 출력한다.
여기서 중요한 점은, 큐 자료구조를 초기화 할 때 배열을 값으로 넣는다.

int[] = {값의 인덱스 정보, 실제 값}

이런 형태의 배열을 큐에 쌓는다.

입력 받은 값을 오름차순으로 정렬하여, Max를 arr[N-1]로 초기화
큐의 자료구조가 비어있을 때까지 반복,
2-1. 큐에서 peek() 한 값이 Max 와 같다면 프린트가 출력된 것이므로 cnt 값 +1,
2-1-1. 만약 peek()한 값의 실제 인덱스가 M과 같다면 cnt 값 출력하고, 로직 종료.
2-1-2. 같지 않다면 Max 값 변경

2-2. 큐에서 peek() 한 값이 Max 보다 작다면, add() 로 다시 추가.

💡코드

public class Main {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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()); // 출력 순서가 궁금한 문서의 인덱스 값

            st = new StringTokenizer(br.readLine());
            int[] arr = new int[N]; 
            LinkedList<int[]> q = new LinkedList<>(); // 정수형 배열을 값으로 같는 큐 선언
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken()); // 문서의 우선순위 (실제 값 정보)
                q.add(new int[]{i, arr[i]}); // 큐에 값을 넣을 때, 인덱스 정보와 실제 값을 넣음
            }
            Arrays.sort(arr); // 최댓값 (우선순위가 높은값) 을 찾기 위해 정렬
            
            int max = arr[N - 1]; // 우선순위가 제일 높은 값을 담을 변수 초기화
            int cnt = 0; // 출력되는 횟수를 위한 변수
      
            while (!q.isEmpty()) {
                int[] tempArr = q.poll(); // 일단 하나를 뽑음.
                if (tempArr[1] < max) { // 배열의 두번 째 값은 실제값(우선순위 값)
                    q.add(tempArr);

                } else if (tempArr[1] == max) {
                    cnt++;
                    if (tempArr[0] == M) {
                        sb.append(cnt).append("\n");
                        break;
                    } else {
                        max = arr[N - 1 - cnt];
                    }
                }
            }
        }
        System.out.println(sb);
    }
}