[백준] Java 1966 프린터 큐

문제

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

알고리즘

구현
자료 구조
시뮬레이션
큐

풀이

우선순위 큐를 이용하여 구현해주면 되는데 몇가지만 주의하면 잘 풀 수 있다.

1. 입력받은 배열을 우선순위 큐에 담아준다.
2. 우선순위가 제일 높은 index 값을 미리 담아준다.
3. 큐가 비어있을 때까지 while문을 돌려준다.
4. 프린터 순서를 체크하기 위한 for문을 돌려주는데 이때 for문의 시작 index는 2번에서 담아준 값으로 한다.
5. 큐의 제일 위에값과 일치하는 값이 나오면 큐에서 값을 하나 빼고 for문의 시작 index를 현재 i값으로 갱신해주고 현재 i값을 방문했다고 체크해준다.
6. 한번 while문이 돌때마다 answer 값을 증가시켜준다.
7. 만약 i값과 몇번째로 인쇄되었는지 궁금한 index값이 같으면 answer 값을 리턴해준다.
8. 만약 첫번째 for문에서 큐의 제일 위에 값을 찾이 못한다면 현재 위치보다 뒤에 있다는 말이므로 for문을 처음부터 다시 돌려준다.
9. 두번째 for문에서 큐의 제일 위에값과 일치하는 값이 나오면 for문의 시작 index를 여기서도 갱신해주고 큐의 값도 하나 빼주고 현재 i값을 방문했다고 체크해준다.
10. 두번째 for문에서도 첫번째와 마찬가지로 i값과 몇번째로 인쇄되었는지 궁금한 index값이 같으면 answer 값을 리턴해준다.

코드

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

class Main {

    public int solution(int[] n, int m) {

        int answer = 1;
        int start = 0;
        int[] visited = new int[n.length];
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

        for (int x : n) {
            queue.offer(x);
        }
        
        for (int i = 0; i < n.length; i++) {
            if (!queue.isEmpty() && queue.peek() == n[i]) {
                start = i;
                break;
            }
        }

        while (!queue.isEmpty()) {
            boolean check = false;
            for (int i = start; i < n.length; i++) {
                if (queue.peek() == n[i] && visited[i] == 0) {
                    queue.poll();
                    start = i;
                    if (i == m) {
                        return answer;
                    }
                    check = true;
                    visited[i] = 1;
                    break;
                }
            }

            if (!check) {
                for (int i = 0; i < n.length; i++) {
                    if (queue.peek() == n[i] && visited[i] == 0) {
                        queue.poll();
                        start = i;
                        if (i == m) {
                            return answer;
                        }
                        visited[i] = 1;
                        break;
                    }
                }
            }

            answer++;
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {

        Main solution = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        ArrayList<Integer> list = new ArrayList<>();
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int[] nn = new int[x];
            StringTokenizer stt = new StringTokenizer(br.readLine());
            for (int j = 0; j < x; j++) {
                nn[j] = Integer.parseInt(stt.nextToken());
            }
            list.add(solution.solution(nn, y));
        }

        for (int x : list) {
            System.out.println(x);
        }
    }
}

ababa