10866: 덱

10866번: 덱(BOJ C/C++)

사용 언어: C

문제

정수를 저장하는 덱(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보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

문제

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

 

풀이

자료구조 카테고리에서 덱을 먼저 설명하기 전에 그냥 덱 관련 문제부터 풀었는데, 이유는 설명할게 딱히 없어서다. 덱은 구조상 원형 큐와 매우 유사한데, 그저 앞에서도 데이터 삽입이 가능하고, 뒤에서도 데이터 삭제가 가능하다는 것이 추가된 것이다. 연결리스트로 구현한 덱과 더 자세한 설명은 덱 구현 글을 따로 써서 올리겠다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 10000

typedef struct Deque {
	int *deque;
	int front, rear, size;
}Deque;

void init_deque(Deque* d)
{
	d->deque = (int*)malloc(sizeof(int)*MAX);
	d->front=0;
	d->rear=0;
	d->size=0;
}

int size(Deque* d)
{
	return d->size;
}

int full(Deque* d)
{
	return ((d->rear+1)%MAX==d->front);
}

int empty(Deque* d)
{
	return (d->front == d->rear);
}

int front(Deque* d)
{
	if(empty(d))
		return -1;
	return d->deque[(d->front+1)%MAX];
}

int back(Deque* d)
{
	if(empty(d))
		return -1;
	return d->deque[d->rear];
}

void push_front(Deque* d, int data) 
{
	if(full(d))
		printf("큐가 포화상태입니다. 데이터 삽입을 취소합니다.\n");
	else
	{
		d->deque[d->front] = data;
		d->front = (d->front-1+MAX) % MAX;	
		d->size++;
	}
}

void push_back(Deque* d, int data) 
{
	if(full(d))
		printf("큐가 포화상태입니다. 데이터 삽입을 취소합니다.\n");
	else
	{
		d->rear = (d->rear+1) % MAX;
		d->deque[d->rear] = data;
		d->size++;
	}
}

int pop_front(Deque* d)
{
	if(empty(d))
		return -1;
	
	d->front=(d->front+1)%MAX;
	d->size--;
	return d->deque[d->front];
}

int pop_back(Deque* d)
{
	if(empty(d))
		return -1;
	
	int tmp=d->deque[d->rear];
	d->rear=(d->rear-1+MAX)%MAX;
	d->size--;
	return tmp;
}

int main(void) 
{
	Deque* deque=(Deque*)malloc(sizeof(Deque));
	init_deque(deque);
	char Get_Com[11];
	int N,num;
	scanf("%d",&N);
	for(int i=0;i<N;i++)
	{
		scanf("%s",Get_Com);
		if(strcmp(Get_Com,"push_front")==0)
		{
			scanf("%d",&num);
			push_front(deque,num);
		}
		else if(strcmp(Get_Com,"push_back")==0)
		{
			scanf("%d",&num);
			push_back(deque,num);
		}
		else if(strcmp(Get_Com,"front")==0)
			printf("%d\n",front(deque));
		else if(strcmp(Get_Com,"back")==0)
			printf("%d\n",back(deque));
		else if(strcmp(Get_Com,"empty")==0)
			printf("%d\n",empty(deque));
		else if(strcmp(Get_Com,"size")==0)
			printf("%d\n",size(deque));
		else if(strcmp(Get_Com,"pop_front")==0)
			printf("%d\n",pop_front(deque));
		else if(strcmp(Get_Com,"pop_back")==0)
			printf("%d\n",pop_back(deque));
	}
	return 0;
}

느낀 점

이 문제를 풀면서 답을 제출했는데 계속 틀려서 1시간을 고민하다가 결국 이유를 알아냈는데,  이 문제를 풀때 이미 만든 원형 큐의 코드에서 추가를 한 것이어서 그때는 main() 함수에서 명령어를 입력할 배열인 Get_Com[] 배열을 Get_Com[10]으로 설정했었다. 근데 push_front 자체가 10글자여서 개행문자까지 입력받으면 10을 넘어서 틀렸었다. 결국 11로 고치고 제출했더니 답이 맞았다... 문제 자체만을 풀 생각말고 문제 풀이에 들어가는 기본적인 문법도 꼼꼼히 따지면서 풀자..!