1966 프린터 큐 JAVA

 

이런 문제를 처음 접해본 나에게 좀 어려웠던 문제이다.

 

https://www.acmicpc.net/problem/1966

 

 

이 문제의 요점은 Queue를 단순히 구현하는 것이 아닌, 각 데이터의 우선 순위도를 비교하여, 우선 순위도가 가장 높은 데이터라면 poll() 즉, 데이터를 제거하는데, 내가 찾으려는 문서와 일치하는 경우엔 이 문서가 몇번째로 빠져나갔는지 체킹을해야한다. 단, 현재 데이터의 우선 순위도가 현재 남은 데이터들의 최고 우선순위도 보다 낮다면, 출력하지 않고 맨 뒤로 보내야한다.

 

내가 작성한 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Q1966 {
    static int T; // 테스트 케이스 수
    static int N; // 문서의 개수
    static int M; // 찾으려는 문서의 인덱스 번호
    static Queue<Integer> queue; // 문서
    static Queue<Integer> indexQ; // 문서 인덱스 번호

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

        T = Integer.valueOf(br.readLine());

        for(int i = 0; i < T; i++) { // 테스트 케이스
            StringTokenizer st = new StringTokenizer(br.readLine(), " "); // 공백 단위로 입력

            N = Integer.valueOf(st.nextToken());
            M = Integer.valueOf(st.nextToken());

            queue = new LinkedList<>();
            indexQ = new LinkedList<>();


            int num = 0;
            st = new StringTokenizer(br.readLine(), " ");
            while(st.hasMoreTokens()) {
                queue.offer(Integer.valueOf(st.nextToken()));
                indexQ.offer(num++);
            }

            result();

        }
    }

    public static void result() {
        int cnt = 1;
        while(true) {
            int max = Collections.max(queue); // 문서 최고 중요도
            int curImport = queue.poll(); // 현재 문서의 중요도
            int curIndex = indexQ.poll(); // 현재 문서의 인덱스 번호

            if(curImport == max) {
                if(curIndex == M) {
                    System.out.println(cnt);
                   break;
                }
                else
                    cnt++;
            }
            else {
                queue.offer(curImport); // 아닌 경우 q와
                indexQ.offer(curIndex); // index를 다시 집어 넣기
            }
        }

    }
}

 

우선 나는 문제에 적힌 기본 변수들은 주석처리를 하였기 때문에 코드를 보면서 이해하는게 좋을거 같고, 중요한 부분부터 바로 설명하겠다.

 

사용자에게로부터, 문서의 갯수와 찾으려는 문서를 입력을 받았다면, 문서들의 인덱스 번호를 indexQ에 초기화 해주고

 queue는 각 문서의 중요도를 저장할건데, 이 문서에 각 문서의 중요도를 입력하여 저장한다.

 

마지막으로 중요한 result()인데, Collections.max()를 이용하면 컬렉션의 가장 높은 값을 얻을 수 있다.

이를 통하여 max 변수에 임시로 저장하고, curImport엔 현재 문서를 빼고, 중요도가 얼마인지 저장한다.

또한 현재 빼낸 문서의 index 번호가 무엇인지도 curIndex 변수에 임시로 저장하였다.

 

이들은 모두 한번 반복될 때 마다, 값이 업데이트 되어야 하므로 반복문 내에 선언하였다.

이렇게 하면 queue의 max 값은 queue의 변경이 있더라도, 새로운 max값을 얻을 수 있다.

 

curImport(현재 문서의 중요도)가 현재 최고 중요도라면 2가지 경우로 나눈다.

 

1. 내가 찾으려는 문서와 일치하는 경우,

2. 내가 찾으려는 문서는 아니지만 최고 중요도인 경우

 

1번 케이스일 때, cnt를 출력하고 반복문을 벗어나게 하였다.

2번 케이스인 경우엔, cnt의 값을 추가하여 빠져나간 문서의 수를 업데이트 한다.

 

 

마지막으로 현재 문서의 중요도가 최고 중요도가 문서가 아닌 경우, 빼냈던 문서를 

다시 맨뒤로 보내버린다.