[백준 10866번] 덱

🔗알고리즘 문제

이 문제는 Deque를 구현하는 문제였는데 처음보는 자료구조여서 로직을 생각해내기 힘들었다,,, 다른 부분은 생각하기 쉬웠지만 push_front일 때 배열에 앞 부분에 값을 추가해야하는데 어떻게 만들어야 할지 감이 안잡혀서 조금 애먹은 문제였다,,

문제 분석

이 문제는 입력으로 주어지는 명령을 처리하는 Deque 자료구조를 구현하는 문제이다.

발상

일반적인 배열에서 인덱스를 활용하여 Deque를 구현할 수 있겠다고 생각했다.

front와 back이라는 각각 자료구조의 맨 앞 인덱스와 맨 뒤 인덱스를 담당하는 변수를 설정한 뒤 각각 인덱스를 알맞게 조절하여 구현하였다.

push_front X: for문을 사용하여 배열의 전체 값을 한칸씩 밀어준 뒤, 맨 앞에 값을 삽입한다.
push_back X: 맨 뒤에 값을 삽입한 후 back을 증가시키기
pop_front: 맨 앞에 있는 값을 출력한 후 front값을 하나 증가시킨다. 만약 deque가 비어있다면 -1을 출력한다.
pop_back: 맨 뒤에 있는 값을 출력한 후 back값을 하나 감소시킨다. 만약 deque가 비어있다면 -1을 출력한다.
size: back - front의 값을 출력한다. ( 현재 Queue의 사이즈 )
empty: front == back의 값을 출력한다.
front: 맨 앞에 있는 값을 출력한다. 만약 deque가 비어있다면 -1을 출력한다.
back: 맨 뒤에 있는 값을 출력한다. 만약 deque가 비어있다면 -1을 출력한다.

알고리즘 설계

1. 입력할 명령의 수를 입력받는다.
2. 명령의 수 만큼 for문을 돌며 명령을 입력받는다.
3. 주어진 명령을 실행한다.

코드

#include<iostream>

using namespace std;

int main(){
    int count;
    cin >> count;

    int* deque = new int[10000];
    int front = -1, back = -1;

    for(int i = 0; i < count; i++){
        string order;
        cin >> order;

        if(order == "push_front"){
            int n;
            cin >> n;
            for(int i = back; i >= 0; i--){
                deque[i + 1] = deque[i];
            }
            back++;
            deque[front + 1] = n;
        }
        else if(order == "push_back"){
            back++;
            int n;
            cin >> n;
            deque[back] = n;
        }
        else if(order == "pop_back" || order == "back"){
            if(back - front == 0) cout << -1 << "\n";
            else{
                cout << deque[back] << "\n";
                if(order == "pop_back") back--;
            }
        }
        else if(order == "pop_front" || order == "front"){
            if(back - front == 0) cout << -1 << "\n";
            else{
                cout << deque[front + 1] << "\n";
                if(order == "pop_front") front++;
            }
        }
        else if(order == "size"){
            cout << back - front << "\n";
        }
        else if(order == "empty"){
            cout << ((back - front == 0) ? 1 : 0) << "\n";
        }
    }
}