[Baekjoon] Queue 풀이 (18258/15828/1966)

18258 - Queue2

package Queue;

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

/*
push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
*/

class Queue2 { //18258

    private static int MAX = 2000000;
    private static int[] queue;
    private static int front = 0;
    private static int rear = 0;
    private static int size = 0;
    private static StringBuilder sb = new StringBuilder();

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

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

        while (n-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String command = st.nextToken();
            if (command.equals("push")) {
                push(Integer.parseInt(st.nextToken()));
            } else if (command.equals("pop")){
                pop();
            }else if (command.equals("size")) {
                size();
            }else if (command.equals("empty")){
                empty();
            }else if (command.equals("front")) {
                front();
            }else if (command.equals("back")) {
                back();
            }

        }

        System.out.println(sb);
    }

    private static void push(int x) {
        queue[rear] = x;
        rear++;
        size++;
    }

    private static void pop() {
        if (size > 0) {
            sb.append(queue[front] + "\n");
            front++;
            size--;
        } else sb.append(-1 + "\n");

    }

    private static void size() {
        sb.append(size + "\n");
    }

    private static void empty() {
        if (size == 0) {
            sb.append(1 + "\n");
        } else sb.append(0 + "\n");
    }

    private static void front() {
        if (size > 0) {
            sb.append(queue[front] + "\n");
        } else sb.append(-1 + "\n");
    }

    private static void back() {
        if (size > 0) {
            sb.append(queue[rear-1] + "\n");
        } else sb.append(-1 + "\n");
    }
}

15828번 - Router

1. 배열 풀이

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


class Main{ //15828

    private static int[] queue;
    private static int front = 0;
    private static int rear = 0;
    private static int size = 0;


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


        int n = Integer.parseInt(br.readLine());
        queue = new int[150000];

        int q_size = n;

        int command = 0;

        while(command != -1){
            command = Integer.parseInt(br.readLine());
            if(command == 0){
                front++;
                size--;
            }else if(command == -1){
                if(size == 0) System.out.println("empty");
                else {
                    while(size-- > 0){
                        sb.append(queue[front]+" ");
                        front++;
                    }
                    System.out.println(sb);
                }
            }else{
                if(size == q_size ) {

                }else {
                    queue[rear] = command;
                    rear++;
                    size++;
                }
            }

        }
    }
}

서브태스크를 만족하려면 배열 크기를 키우면 되지만 그냥 Queue 클래스를 쓰는 게 맞는 풀이 같다

2. Queue 클래스 풀이

package Queue;

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

class Router{ //15828

    private static int front = 0;
    private static int rear = 0;
    private static int size = 0;


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

        Queue<Integer> queue = new LinkedList<>();

        int n = Integer.parseInt(br.readLine());
        int q_size = n;

        int command = 0;

        while(command != -1){
            command = Integer.parseInt(br.readLine());
            if(command == 0){
                queue.poll();
                size--;
            }else if(command == -1){
                if(size == 0) System.out.println("empty");
                else {
                    while(size-- > 0){
                        sb.append(queue.poll()+" ");
                    }
                    System.out.println(sb);
                }
            }else{
                if(size == q_size ) {

                }else {
                    queue.add(command);
                    size++;
                }
            }

        }
    }
}

1966번 - 프린터큐

package Queue;

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

/*
[테스트 케이스-T]
[문서의 개수-N] [출력순서가 궁금한 문서의 위치-pos]
[N개의 문서 중요도(중요도 중복가능)]
 */

public class PrinterQueue {

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

        StringBuilder sb = new StringBuilder();

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

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


        while (T-- > 0) {
            //n, 위치
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int pos = Integer.parseInt(st.nextToken());


            // 위치, 중요도를 가진 큐 생성
            LinkedList<int[]> queue = new LinkedList<>();

            st = new StringTokenizer(br.readLine());

            for (int i = 0; i < n; i++) {
                int command = Integer.parseInt(st.nextToken());
                queue.add(new int[]{i, command});
            }
            int count = 0;
            while (!queue.isEmpty()) { //큐에 원소가 있을 때 까지
                boolean isMax = true;
                int[] front = queue.poll();
                for (int i = 0; i < queue.size(); i++) {
                    if (front[1] < queue.get(i)[1]) { //첫 원소의 중요도보다 i번째 중요도가 클 경우
                        queue.add(front); //맨앞 원소를 맨뒤로
                        for (int j = 0; j < i; j++) {
                            queue.add(queue.poll()); //큰 원소 전까지 빼서 새로 넣기
                        }
                        isMax = false;
                        break;
                    }
                }
                if (!isMax) {
                    continue;
                } else { //첫 원소가 젤 크면 count로 체크
                    count++;
                    if (front[0] == pos) break; // 문제에서 주어진 위치면
                }

            }
            sb.append(count + "\n");
        }
        System.out.println(sb);
    }
}

1966 참고: https://st-lab.tistory.com/201