BOJ 10866 : 덱

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/10866

 

참고

- BOJ 10866 : 덱 with Linked List

 

 

큐 + 스택 문제를 조합해서 풀면 해결할 수 있다.

큐에서 push할 때는 wp++, pop은 rp++이고,

스택에서 push할 때는 sp++, pop은 --sp였다.

 

즉, 배열의 앞에서 pop할 때는 rp++, 뒤에서 pop할 때는 --wp를 하면 된다.

마찬가지로, 앞에서 push할 때는 --rp, 뒤에서 push wp++ 이 된다.

 

덱의 경우, 앞에서도 push가 가능하므로 rp : read pointer의 의미가 맞지 않다.

따라서, 혼동되지 않도록 rp → front, wp → back 으로 수정하였다.

 

메모리를 넉넉하게 잡고 메모리의 가운데 부터 시작점을 정하면 index가 넘어가는 것을 피할 수 있다.

N이 최대 10,000이라서 넉넉히 배열의 크기를 5만 정도 잡았다.

#include <stdio.h>

int N;
int deque[50000 + 500];
int front, back;

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

int main(void)
{
	int input;
	char str[15];

	scanf("%d", &N);

	front = back = 25000;
	for (int i = 0; i < N; i++)
	{
		scanf("%s", str);

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

	return 0;
}