📝 문제 설명

정수를 저장하는 덱을 구현하고, 덱에서 사용 되는 8가지 커맨드를 구현하라.

push_front X: 정수 X를 덱의 앞에 넣는다.
push_back X: 정수 X를 덱의 뒤에 넣는다.
pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 덱에 들어있는 정수의 개수를 출력한다.
empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

💡 아이디어

자바 공식 문서의 권장에 따라 ArrayDeque을 사용하여 덱을 구현한다. 공식 문서
if - else로 예외 처리를 해두긴 했지만, 더 안정적인 함수인 .poll.peek을 사용하여 커맨드를 구현한다.

🛠 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Deque<Integer> deque = new ArrayDeque<>();

        while (N-- > 0) {
            String command = br.readLine();

            // [1] push_front
            if (command.startsWith("push_front")) {
                int X = Integer.parseInt(command.split(" ")[1]);
                deque.addFirst(X); // 덱 앞에 삽입

                // [2] push_back
            } else if (command.startsWith("push_back")) {
                int X = Integer.parseInt(command.split(" ")[1]);
                deque.addLast(X); // 덱 뒤에 삽입

                // [3] pop_front
            } else if (command.equals("pop_front")) {
                if (!deque.isEmpty()) {
                    System.out.println(deque.pollFirst());
                } else {
                    System.out.println(-1);
                }

                // [4] pop_back
            } else if (command.equals("pop_back")) {
                if (!deque.isEmpty()) {
                    System.out.println(deque.pollLast());
                } else {
                    System.out.println(-1);
                }

                // [5] size
            } else if (command.equals("size")) {
                System.out.println(deque.size());

                // [6] empty
            } else if (command.equals("empty")) {
                System.out.println((deque.isEmpty()) ? 1 : 0);

                // [7] front
            } else if (command.equals("front")) {
                if (!deque.isEmpty()) {
                    System.out.println(deque.peekFirst());
                } else {
                    System.out.println(-1);
                }

                // [8] back
            } else if (command.equals("back")) {
                if (!deque.isEmpty()) {
                    System.out.println(deque.peekLast());
                } else {
                    System.out.println(-1);
                }
            }
        }
    }
}

⏱ 시간복잡도

총 커맨드의 수를 N이라 할 때, 각 명령어는 ArrayDeque의 메서드 (addFirst, pollLast, peekFirst 등)를 사용하므로 각 연산은 O(1) 시간에 수행된다.
따라서 전체 커맨드에 대한 총 시간 복잡도는 O(N) 이다.

✏️ 느낀 점

스택, 큐, 덱을 구현하는 기초 3문제를 전부 풀었는데, 많은 도움이 된 것 같다.
유사 문제는 스스로 발상이 가능해졌다.