백준 [1966] 프린터 큐

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

1966번: 프린터 큐

 

처음 우선순위 큐를 사용해서 접근하려고 했으나 해결이 안되었다. 풀이 중 LinkedList를 큐처럼 사용하는 방법이 있었다.

 

Queue<> q = new LinkedList<>(); 가 아닌 LinkedList<> = new LinkedList<>(); 로 선언하면 큐처럼 add(), poll()을 할 수 있고 반복문으로 탐색이 가능하였다.

 

문제는 N개를 입력받는데 순서와 중요도가 존재한다. 중요도 값은 중복이 될 수 있다.

N과 함께 입력 받은 M은 현재 queue에서 몇 번째로 놓여있는지를 나타내는 인덱스가 있다.

 

출력되는 차례의 인덱스가 M이랑 같을 때 그 출력 순서를 구하는 문제이다.

 

풀이

 

처음 입력 받을 때 입력 순서와 순서에 해당하는 중요도를 저장할 Node라는 객체를 선언하였다.

 

1. 처음 큐에서 데이터를 뽑는다.

2. 해당 Node 중요도 보다 더 큰 중요도를 가지고 있는지 나머지 큐의 데이터를 돌면서 탐색한다.

  2-1. 중요도가 더 큰 데이터가 나왔을 때 
          하나라도 큰 데이터가 있으면 현재 뽑힌 데이터는 다시 큐에 넣고 뽑힌 더 큰 데이터에 대해서 2번 탐색을 시작한다.

  2-2. 해당 Node가 중요도가 가장 클 때

          이 Node는 poll()을 하고 이 때 Node의 순서가 M과 같은지 검사하고 일치하면 출력 순서 번호를 출력한다.

3. 아니라면 1번부터 반복

 

 

전체 코드

package com.baekjoon.p1966;

import java.io.*;
import java.util.*;

public class Main {
    static int ans;

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

        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            st = new StringTokenizer(br.readLine());

            ans = 0;
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken()); // 뽑고자 하는 순서 번호

            LinkedList<Node> q = new LinkedList<>(); // 큐처럼 활용할 리스트
            st = new StringTokenizer(br.readLine());

            for (int i = 0; i < N; i++) {
                q.add(new Node(i, Integer.parseInt(st.nextToken())));
            }

            while (!q.isEmpty()) {

                Node target = q.poll();
                boolean flag = true;

                for (int i = 0; i < q.size(); i++) {

                    if (target.value < q.get(i).value) { // 큐에 더 큰 중요도가 존재하면
                        q.add(target); // 제일 뒤로 넣기

                        for (int j = 0; j < i; j++) { // 큰 중요도에 해당하는 큐만큼 뽑고 다시 넣기를 반복
                            q.add(q.poll());
                        }

                        flag = false;
                        break;
                    }

                }

                if (!flag) {
                    continue;
                }

                ans++;

                if (target.rank == M) {
                    break;
                }
            }
            sb.append(ans + "\n");
        }

        System.out.println(sb);

    }
}

class Node {
    int rank;
    int value;

    Node(int rank, int value) {
        this.rank = rank;
        this.value = value;
    }
}