문제
정수를 저장하는 덱(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보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
예제 입력 1
15 push_back 1 push_front 2 front back size empty pop_front pop_back pop_front size empty pop_back push_front 3 empty front |
예제 출력 1
2 1 2 0 2 1 -1 0 1 -1 0 3 |
예제 입력 2
22 front back pop_front pop_back push_front 1 front pop_back push_back 2 back pop_front push_front 10 push_front 333 front back pop_back pop_back push_back 20 push_back 1234 front back pop_back pop_back |
예제 출력 2
-1 -1 -1 -1 1 1 2 2 333 10 10 333 20 1234 1234 20 |
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<string.h>
typedef int element;
typedef struct DlistNode
{
element data;
struct DlistNode *llink;
struct DlistNode *rlink;
}
DlistNode;
void init(DlistNode *phead)
{
phead->llink=phead;
phead->rlink=phead;
phead->data=-1;
}
void push_front(DlistNode *before,DlistNode *new_node)
{
while(before->llink->data!=-1)
before=before->llink;
new_node->llink=before->llink;
new_node->rlink=before;
before->llink->rlink=new_node;
before->llink=new_node;
}
void push_back(DlistNode *before,DlistNode *new_node)
{
while(before->rlink->data!=-1)
before=before->rlink;
new_node->llink=before;
new_node->rlink=before->rlink;
before->rlink->llink=new_node;
before->rlink=new_node;
}
void dremove_node(DlistNode *phead_node,DlistNode *removed)
{
if(removed==phead_node)
return;
removed->llink->rlink=removed->rlink;
removed->rlink->llink=removed->llink;
free(removed);
}
int pop_front(DlistNode *phead_node)
{
int N=phead_node->rlink->data;
dremove_node(phead_node,phead_node->rlink);
return N;
}
int pop_back(DlistNode *phead_node)
{
int N=phead_node->llink->data;
dremove_node(phead_node,phead_node->llink);
return N;
}
int front(DlistNode *phead_node)
{
return phead_node->rlink->data;
}
int back(DlistNode *phead_node)
{
return phead_node->llink->data;
}
int main(void)
{
DlistNode head_node, **deque=NULL;
int N, size=0, num;
scanf("%d", &N);
while(getchar()!='\n');
deque=(DlistNode **)malloc(sizeof(DlistNode *)*N);
init(&head_node);
for(int i=0;i<N;i++)
{
char command[30]={'\0', };
fgets(command,sizeof(command),stdin);
deque[i]=(DlistNode *)malloc(sizeof(DlistNode));
if(strncmp(command,"push_front",10)==0)
{
for(int j=11;command[j]!='\0';j++)
command[j-11]=command[j];
deque[i]->data=atoi(command);
push_front(&head_node,deque[i]);
size++;
}
else if(strncmp(command,"push_back",9)==0)
{
for(int j=10;command[j]!='\0';j++)
command[j-10]=command[j];
deque[i]->data=atoi(command);
push_back(&head_node,deque[i]);
size++;
}
else if(strncmp(command,"pop_front",9)==0)
{
num=pop_front(&head_node);
printf("%d\n", num);
free(deque[i]);
size-=num!=-1;
}
else if(strncmp(command,"pop_back",8)==0)
{
num=pop_back(&head_node);
printf("%d\n", num);
free(deque[i]);
size-=num!=-1;
}
else if(strncmp(command,"size",4)==0)
{
printf("%d\n", size);
free(deque[i]);
}
else if(strncmp(command,"front",5)==0)
{
printf("%d\n", front(&head_node));
free(deque[i]);
}
else if(strncmp(command,"back",4)==0)
{
printf("%d\n", back(&head_node));
free(deque[i]);
}
else if(strncmp(command,"empty",5)==0)
{
printf("%d\n", size==0);
free(deque[i]);
}
else
{
printf("error\n");
free(deque[i]);
}
}
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 13015번: 별 찍기 - 23 (0) | 2020.07.30 |
---|---|
<백준 알고리즘> 9507번: Generations of Tribble (0) | 2020.07.30 |
<백준 알고리즘> 1237번: 정ㅋ벅ㅋ (0) | 2020.07.26 |
<백준 알고리즘> 19532번: 수학은 비대면강의입니다 (0) | 2020.07.26 |
<백준 알고리즘> 2750번: 수 정렬하기 (0) | 2020.07.25 |