알고리즘 문제
[C/C++ 백준 10866번] 덱 (Silver 4)
새파란 공대생
2020. 8. 11. 15:14
https://www.acmicpc.net/problem/10866
10866번: 덱
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 ��
www.acmicpc.net
배열을 기반으로 구현해보았다.
#include <cstdio>
#include <cstring>
class Deque{
private:
int array[10000]={};
int i=0;
public:
void push_back(int X){
array[i++]=X;
}
void push_front(int X){
for(int j=i; j>0; j--){
array[j]=array[j-1];
}
array[0]=X;
i++;
}
void pop_front(){
if(i==0)
printf("-1\n");
else{
int temp = array[0];
for(int j=0; j<i-1; j++)
array[j]=array[j+1];
i--;
printf("%d\n",temp);
}
}
void pop_back(){
if(i==0)
printf("-1\n");
else{
int temp = array[i-1];
i--;
printf("%d\n",temp);
}
}
void size(){
printf("%d\n", i);
}
void empty(){
if(i>0)
printf("0\n");
else
printf("1\n");
}
void front(){
if(i==0)
printf("-1\n");
else
printf("%d\n", array[0]);
}
void back(){
if(i==0)
printf("-1\n");
else
printf("%d\n", array[i-1]);
}
};
int main(void){
int N, num;
Deque q;
char str[100];
char push_back[] = "push_back";
char push_front[] = "push_front";
char front[] = "front";
char back[] = "back";
char size[] = "size";
char empty[] = "empty";
char pop_front[] = "pop_front";
char pop_back[] = "pop_back";
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf(" %s",str);
if(strcmp(str, push_back)==0){
scanf(" %d",&num);
q.push_back(num);
}
if(strcmp(str, push_front)==0){
scanf(" %d",&num);
q.push_front(num);
}
if(strcmp(str, front)==0){
q.front();
}
if(strcmp(str, back)==0){
q.back();
}
if(strcmp(str, size)==0){
q.size();
}
if(strcmp(str, empty)==0){
q.empty();
}
if(strcmp(str, pop_front)==0){
q.pop_front();
}
if(strcmp(str, pop_back)==0){
q.pop_back();
}
}
}STL에 있는 deque를 사용하면 다음과 같다.
#include <cstdio>
#include <cstring>
#include <deque>
using namespace std;
int main(void){
int N, num;
deque<int> dq;
char str[100];
char push_back[] = "push_back";
char push_front[] = "push_front";
char front[] = "front";
char back[] = "back";
char size[] = "size";
char empty[] = "empty";
char pop_front[] = "pop_front";
char pop_back[] = "pop_back";
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf(" %s",str);
if(strcmp(str, push_back)==0){
scanf(" %d",&num);
dq.push_back(num);
}
if(strcmp(str, push_front)==0){
scanf(" %d",&num);
dq.push_front(num);
}
if(strcmp(str, front)==0){
if(dq.empty())
printf("-1\n");
else
printf("%d\n", dq.front());
}
if(strcmp(str, back)==0){
if(dq.empty())
printf("-1\n");
else
printf("%d\n", dq.back());
}
if(strcmp(str, size)==0){
printf("%d\n", dq.size());
}
if(strcmp(str, empty)==0){
if(dq.empty())
printf("1\n");
else
printf("0\n");
}
if(strcmp(str, pop_front)==0){
if(dq.empty())
printf("-1\n");
else{
printf("%d\n", dq.front());
dq.pop_front();
}
}
if(strcmp(str, pop_back)==0){
if(dq.empty())
printf("-1\n");
else{
printf("%d\n", dq.back());
dq.pop_back();
}
}
}
}