BOJ 10866 : 덱 (deque)

삼성 B형 전체 링크

 

https://www.acmicpc.net/problem/10866

 

 

vector로 동적 배열, 링크드 리스트를 이용할 수 있다.

그러나 vector는 끝에만 원소를 추가할 수 있으므로, 앞에도 원소를 추가해야할 경우에는 덱(deque)을 사용해보자.

스택(stack), 큐(queue)는 배열로 만드는 것이 쉽고 충분하지만,

덱(deque)의 경우는 pure하게 만들 때, 메모리 관리에 이슈가 있을 수 있다.

---

deque에서 자주 사용하는 메서드는 아래와 같다.

clear()	deque를 초기화 한다.
push_front()	앞에 원소를 넣는다.
push_back()	뒤에 원소를 넣는다. vector와 동일하다.
pop_front()	앞의 원소를 뺀다.
pop_back()	뒤의 원소를 뺀다.
size()	deque의 크기를 return 한다.
empty()	deque가 비어있으면 true, 아니면 false를 return 한다.
front()	가장 앞의 원소를 return 한다.
back()	가장 뒤의 원소를 return 한다.

 

위의 메서드를 이용하여 BOJ 10866 : 덱을 풀 수 있다.

#include <stdio.h>
#include <iostream>
#include <deque>

using namespace std;

deque<int> dq;

int mystrcmp(const char *a, const char *b)
{
    while (*a && *a == *b) ++a, ++b;
    return *a - *b;
}

int main(void)
{
    int in, N, size;
    char str[15];

    scanf("%d", &N);

    dq.clear(); /* 초기화 */
    for (int i = 0; i < N; i++)
    {
        scanf("%s", str);

        if (mystrcmp(str, "push_front") == 0)
        {
            scanf("%d", &in);
            dq.push_front(in);
        }
        else if (mystrcmp(str, "push_back") == 0)
        {
            scanf("%d", &in);
            dq.push_back(in);
        }
        else if (mystrcmp(str, "pop_front") == 0)
        {
            if (dq.size() == 0) printf("-1\n");
            else
            {
                printf("%d\n", dq.front());
                dq.pop_front();
            }
        }
        else if (mystrcmp(str, "pop_back") == 0)
        {
            if (dq.size() == 0) printf("-1\n");
            else
            {
                printf("%d\n", dq.back());
                dq.pop_back();
            }
        }
        else if (mystrcmp(str, "size") == 0)
            printf("%d\n", dq.size());
        else if (mystrcmp(str, "empty") == 0)
            printf("%d\n", dq.empty());
        else if (mystrcmp(str, "front") == 0)
            printf("%d\n", (dq.size() == 0) ? -1 : dq.front());
        else if (mystrcmp(str, "back") == 0)
            printf("%d\n", (dq.size() == 0) ? -1 : dq.back());
    }

    return 0;
}