[BOJ] 19단계 큐, 덱

1

18258

큐 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        StringBuilder sb = new StringBuilder();
        CustomQueue queue = new CustomQueue();
        for(int i = 0; i < n; i++) {
            String[] split = reader.readLine().split(" ");
            switch (split[0]) {
                case "push":
                    queue.push(Integer.parseInt(split[1]));
                    break;
                case "front":
                    sb.append(queue.front()).append("\n");
                    break;
                case "back":
                    sb.append(queue.back()).append("\n");
                    break;
                case "size":
                    sb.append(queue.size()).append("\n");
                    break;
                case "pop":
                    sb.append(queue.pop()).append("\n");
                    break;
                case "empty":
                    sb.append(queue.empty()).append("\n");
                    break;
            }
        }
        System.out.print(sb);
    }

    static class CustomQueue {
        Queue<Integer> queue = new LinkedList<>();
        int back = -1;

        public void push(int x) {
            queue.offer(x);
            back = x;
        }

        public int pop() {
            if(queue.isEmpty()) {
                return -1;
            }
            return queue.poll();
        }

        public int front() {
            if(queue.isEmpty()) {
                return -1;
            }
            return queue.peek();
        }

        public int back() {
            if(queue.isEmpty()) {
                return -1;
            }
            return back;
        }

        public int empty() {
            if(queue.isEmpty()) {
                return 1;
            }
            return 0;
        }

        public int size() {
            return queue.size();
        }
    }
}

*Queue 구현체로 LinkedList 사용

*poll(): remove()

*peek(): get()

*offer(): add()

 

2

2164

카드2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i <= n; i++) {
            queue.add(i);
        }
        while(queue.size() > 1) {
            queue.poll();
            queue.add(queue.poll());
        }
        System.out.print(queue.peek());
    }
}

 

3

11866

요세푸스 문제 0

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        int N = Integer.parseInt(split[0]);
        int K = Integer.parseInt(split[1]);
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i <= N; i++) {
            queue.offer(i);
        }
        StringBuilder sb = new StringBuilder();
        sb.append("<");
        while(queue.size() > 0) {
            for(int i = 0; i < K-1; i++) {
                queue.offer(queue.poll());
            }
            sb.append(queue.poll()).append(", ");
        }
        System.out.print(sb.substring(0, sb.length()-2) + ">");
    }
}

 

4

1966

프린터 큐

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < T; i++) {
            Queue<Integer> queue = new LinkedList<>();
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int N = Integer.parseInt(tokenizer.nextToken());
            int M = Integer.parseInt(tokenizer.nextToken());
            for(int j = 0; j < N; j++) {
                queue.offer(j);
            }
            tokenizer = new StringTokenizer(reader.readLine());
            int[] priority = new int[N];
            for(int j = 0; j < priority.length; j++) {
                priority[j] = Integer.parseInt(tokenizer.nextToken());
            }

            int cnt = 0;
            while(!queue.isEmpty()) {
                Integer front = queue.poll();
                boolean isMax = true;
                for (int p : priority) {
                    if (priority[front] < p) {
                        isMax = false;
                        break;
                    }
                }
                if(isMax) {
                    //큐에서 제거되었기 때문에 중요도를 0으로 초기화
                    priority[front] = 0;
                    cnt++;
                    if(front == M) {
                        sb.append(cnt).append("\n");
                        break;
                    }
                } else {
                    //중요도가 최대가 아니면 큐에 다시 삽입
                    queue.offer(front);
                }
            }
        }
        System.out.print(sb);
    }
}

 

5

10866

덱

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(reader.readLine());
        CustomDeque deque = new CustomDeque();
        for(int i = 0; i < n; i++) {
            String[] split = reader.readLine().split(" ");
            switch (split[0]) {
                case "push_front":
                    deque.pushFront(Integer.parseInt(split[1]));
                    break;
                case "push_back":
                    deque.pushBack(Integer.parseInt(split[1]));
                    break;
                case "pop_front":
                    sb.append(deque.popFront()).append("\n");
                    break;
                case "pop_back":
                    sb.append(deque.popBack()).append("\n");
                    break;
                case "size":
                    sb.append(deque.size()).append("\n");
                    break;
                case "empty":
                    sb.append(deque.empty()).append("\n");
                    break;
                case "front":
                    sb.append(deque.front()).append("\n");
                    break;
                case "back":
                    sb.append(deque.back()).append("\n");
                    break;
            }
        }
        System.out.print(sb);
    }

    static class CustomDeque {
        Deque<Integer> deque = new LinkedList<>();

        public void pushFront(int x) {
            deque.addFirst(x);
        }

        public void pushBack(int x) {
            deque.addLast(x);
        }

        public int popFront() {
            if(deque.isEmpty()) {
                return -1;
            } else {
                return deque.removeFirst();
            }
        }

        public int popBack() {
            if(deque.isEmpty()) {
                return -1;
            } else {
                return deque.removeLast();
            }
        }

        public int size() {
            return deque.size();
        }

        public int empty() {
            if(deque.isEmpty()) {
                return 1;
            } else {
                return 0;
            }
        }

        public int front() {
            if(deque.isEmpty()) {
                return -1;
            } else {
                return deque.peekFirst();
            }
        }

        public int back() {
            if(deque.isEmpty()) {
                return -1;
            } else {
                return deque.peekLast();
            }
        }
    }
}

*Deque 구현체로 LinkedList 사용

 

6

1021

회전하는 큐

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());
        int M = Integer.parseInt(tokenizer.nextToken());
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 1; i <= N; i++) {
            deque.add(i);
        }
        tokenizer = new StringTokenizer(reader.readLine());
        int cnt = 0;
        for(int i = 0; i < M; i++) {
            int num = Integer.parseInt(tokenizer.nextToken());
            int rotateLeft = 0;
            while(!deque.isEmpty()) {
                if(deque.peekFirst() == num) {
                    int rotateRight = deque.size() - rotateLeft;
                    cnt += Math.min(rotateLeft, rotateRight);
                    deque.pollFirst();
                    break;
                } else {
                    //rotate left
                    deque.offerLast(deque.pollFirst());
                    rotateLeft++;
                }
            }
        }
        System.out.print(cnt);
    }
}

*회전하는 연산이기 때문에 한쪽 방향에 대한 회전 횟수로 다른 방향에 대한 회전 횟수 계산 가능

 

7

5430

AC

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            String func = reader.readLine();
            int n = Integer.parseInt(reader.readLine());

            Deque<Integer> deque = new LinkedList<>();
            String arrStr = reader.readLine();
            StringTokenizer tokenizer = new StringTokenizer(arrStr.substring(1, arrStr.length() - 1), ",");

            for(int j = 0; j < n; j++) {
                deque.add(Integer.parseInt(tokenizer.nextToken()));
            }

            boolean reverse = false;
            boolean error = false;
            for (int j = 0; j < func.length(); j++) {
                char c = func.charAt(j);
                if (c == 'R') {
                    reverse = !reverse;
                } else if(deque.isEmpty()) {
                    error = true;
                    break;
                } else if (reverse) {
                    deque.pollLast();
                } else {
                    deque.pollFirst();
                }
            }

            if(error) {
                sb.append("error\n");
            } else {
                sb.append("[");
                while(!deque.isEmpty()) {
                    if(reverse) {
                        sb.append(deque.pollLast());
                    } else {
                        sb.append(deque.pollFirst());
                    }
                    if(!deque.isEmpty()) {
                        sb.append(",");
                    }
                }
                sb.append("]\n");
            }
        }
        System.out.print(sb);
    }
}