[JAVA/10866번] 덱(Deque)

---

문제

---

입력 및 출력

---

풀이

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

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

        // DEQUE
        int[] deque = new int[N];

        // FRONT INDEX, BACK INDEX
        int frontIndex = (int) Math.floor(N / 2);
        int backIndex = ((int) Math.floor(N / 2)) - 1;

        while (N-- > 0) {
            String[] input = br.readLine().split(" ");

            switch (input[0]) {
                case "push_front":
                    if (frontIndex == 0) {
                        deque[frontIndex] = Integer.parseInt(input[1]);
                    } else {
                        frontIndex--;
                        deque[frontIndex] = Integer.parseInt(input[1]);
                    }
                    break;
                case "push_back":
                    backIndex++;
                    deque[backIndex] = Integer.parseInt(input[1]);
                    break;
                case "pop_front":
                    if (frontIndex > backIndex) {
                        System.out.println(-1);
                    } else {
                        System.out.println(deque[frontIndex]);
                        frontIndex++;
                    }
                    break;
                case "pop_back":
                    if (frontIndex > backIndex) {
                        System.out.println(-1);
                    } else {
                        System.out.println(deque[backIndex]);
                        backIndex--;
                    }
                    break;
                case "front":
                    if (frontIndex > backIndex) {
                        System.out.println(-1);
                    } else {
                        System.out.println(deque[frontIndex]);
                    }
                    break;
                case "back":
                    if (frontIndex > backIndex) {
                        System.out.println(-1);
                    } else {
                        System.out.println(deque[backIndex]);
                    }
                    break;
                case "size":
                    System.out.println((backIndex + 1) - frontIndex);
                    break;
                case "empty":
                    if (frontIndex > backIndex) {
                        System.out.println(1);
                    } else {
                        System.out.println(0);
                    }
                    break;
            }
        }
    }
}

---

결과 및 해결방법

[결과]

[정리]

해결방법

• LinkedList를 이용하여 쉽게 구현할 수 있지만, 나는 배열을 사용하여 구현하였다.

  문제를 해결하기 위한 핵심은 인덱스의 위치 설정이었다. 왜냐하면, Deque는 원소를 앞과 뒤로 넣을 수 있기 때문이다. 즉 Stack과 Queue의 특징을 모두 가진 자료구조라고 할 수 있다.

  배열로 문제를 해결하기 위해 앞쪽 위치를 가리키기 위한 frontIndex 뒤쪽 위치를 가리키기 위한 backIndex로 구성했다.

  frontIndex는 N/2의 인덱스 위치를 갖고, backIndex는 (N/2)-1의 인덱스 위치를 갖는다. backIndex에 -1을 하는 이유는 Deque가 비어있음을 판단하기 위함이다.

• push_front명령어의 경우, frontIndex가 0이라면 Deque의 상태는 비어있는 것이고 해당 인덱스에 입력받은 숫자를 넣어주었다.

  그 외의 경우는 frontIndex의 값을 1 감소하고 Deque의 해당 인덱스에 입력받은 숫자를 넣어주었다.

• push_back명령어의 경우, Deque에 가장 뒤에 원소를 넣는 것이기 때문에 backIndex를 1 증가시키고 Deque의 해당 인덱스에 값을 넣어주었다.

• pop_front명령어의 경우, frontIndex의 위치에 존재하는 값을 출력하고, frontIndex를 1 증가시켜주었다.

• pop_back명령어의 경우, backIndex의 위치에 존재하는 값을 출력하고, backIndex를 1 감소시켜주었다.

• size명령어의 경우, 전체 크기는 backIndex에 1을 더한 값에서 frontIndex를 뺀 값이다.

  여기서, backIndex에 1을 더한 이유는 배열의 인덱스는 0부터 시작하기 때문이다.

• 그 외의 명령어는 위의 명령어와 겹치는 부분이므로 생략한다.