[JAVA 알고리즘]BAEKJOON 10866번 덱

덱

---

문제 설명

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

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

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

제한사항

• 없음

입출력 예

input	return
15 push_back 1 push_front 2 front back size empty pop_front pop_back pop_front size empty pop_back push_front 3 empty front	2 1 2 0 2 1 -1 0 1 -1 0 3

---

문제 분석

문제에 주어진 대로 구현을 해서 문제 분석은 따로 하지 않았다.

나의 문제풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();

        int total = Integer.parseInt(bufferedReader.readLine());

        // 주어진 개수만큼의 배열 선언
        String[] deque = new String[total];
        int start = 0;
        int end = 0;
        for (int i = 0; i < total; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            String command = stringTokenizer.nextToken();
            switch (command) {
                case "push_front":
                    // 시작 위치와 마지막 위치가 다르면 값이 있다.
                    if (start != end) {
                        // 마지막 위치부터 시작 위치까지 하나씩 뒤로 옮긴 후, 시작 위치에 입력값을 넣는다.
                        for (int j = end - 1; j >= start; j--) {
                            deque[j + 1] = deque[j];
                        }
                        deque[start] = stringTokenizer.nextToken();
                        // 입력값이 하나 늘었기 때문에 마지막 위치도 올린다.
                        end++;
                    } else { // 입력값을 넣고 값의 마지막 위치 인덱스를 올린다.
                        deque[end++] = stringTokenizer.nextToken();
                    }
                    break;
                case "push_back":
                    // 입력값을 넣고 값의 마지막 위치 인덱스를 올린다.
                    deque[end++] = stringTokenizer.nextToken();
                    break;
                case "pop_front":
                    // 입력값이 있으면 시작 위치의 값을 출력하고 시작 위치값을 올린다.
                    if (start != end) {
                        stringBuilder.append(deque[start++]).append("\n");
                    } else {
                        // 입력 값이 없으면 -1 출력
                        stringBuilder.append("-1\n");
                    }
                    break;
                case "pop_back":
                    // 입력값이 있으면 마지막 위치 -1의 값을 출력하고 마지막 위치값을 내린다.
                    if (start != end) {
                        stringBuilder.append(deque[end - 1]).append("\n");
                        end--;
                    } else {
                        stringBuilder.append("-1\n");
                    }
                    break;
                case "size":
                    // 마지막 위치와 시작 위치의 차이로 입력값의 갯수를 출력한다.
                    stringBuilder.append(end - start).append("\n");
                    break;
                case "empty":
                    if (start != end) {
                        stringBuilder.append("0\n");
                    } else {
                        stringBuilder.append("1\n");
                    }
                    break;
                case "front":
                    // 입력값이 있으면 시작 위치의 값을 출력한다.
                    if (start != end) {
                        stringBuilder.append(deque[start]).append("\n");
                    } else {
                        stringBuilder.append("-1\n");
                    }
                    break;
                case "back":
                    // 입력값이 있으면 마지막 위치 -1의 값을 출력한다.
                    if (start != end) {
                        stringBuilder.append(deque[end-1]).append("\n");
                    } else {
                        stringBuilder.append("-1\n");
                    }
                    break;
            }
        }
        bufferedReader.close();

        System.out.println(stringBuilder);
    }
}

컬렉션으로 덱을 지원을 하고 있지만 덱을 이해 해보기 위해서 배열을 이용해서 덱을 구현을 해보았다.
컬렉션으로 지원하는 덱은 노드로 구현되어 있는 것으로 봤는데, 배열을 이용해서 만들었을 때 보다 더 빠르게 작동을 했다. 내가 구현을 잘 못했는지 모르겠지만 그래도 어떤 식으로 작동을 하는지 이해가 좀 더 된 것 같고 덱을 만들어 봤지만 큐와 스택도 같이 알 수 있었다. 

---

알고리즘 분류

• 구현
• 자료 구조
• 덱

문제 출처 - https://www.acmicpc.net/problem/10866

10866번: 덱