[백준 C언어] 10866. 덱

문제

 

정수를 저장하는 덱(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>


typedef struct node {  //이중 연결 리스트를 위한 구조체 정의
	int key;
	struct node* next;
	struct node* prev;
}node;

node* head, *tail;

void init() {	//덱 초기화. 시작과 끝 더미노드를 만들고, 서로를 prev/next포인터로 지정
	head = (node*)malloc(sizeof(node));
	tail = (node*)malloc(sizeof(node));
	head->prev = head;
	head->next = tail;
	tail->prev = head;
	tail->next = tail;
}

void push_front(int n) {  //시작 노드 다음에 노드 연결
	node* p, * s;
	s = head->next;
	p = (node*)malloc(sizeof(node));
	p->key = n;

	p->next = s;
	s->prev = p;
	head->next = p;
	p->prev = head;
}

void push_back(int n) { //끝 노드 전에 노드 연결
	node* p, * s;
	s = tail->prev;
	p = (node*)malloc(sizeof(node));
	p->key = n;

	p->prev = s;
	s->next = p;
	p->next = tail;
	tail->prev = p;
}

int size(void) {  //시작 노드의 다음이 끝 노드가 아닐 경우 카운트하여 반환
	int cnt = 0; //덱이 비어있을 경우 그대로 반환하기 위해 0으로 초기화
	if (head->next != tail)
	{
		node* s = head;
		while (s->next != tail) {
			s = s->next;
			cnt++;
		}
	}

	return cnt;
}

int empty(void) { //시작 노드의 다음이 끝 노드일 경우 1 반환
	return head->next == tail;
}

int pop_front(void) { //시작 노드의 다음 노드 키값 반환 및 노드 삭제
	int i = -1; //덱이 비어있을 경우 그대로 반환하기 위해 -1로 초기화
	if (!empty()) {
		node* t = head->next;
		i = t->key;
		head->next = t->next;
		t->next->prev = head;
		free(t);
	}
	return i;
}

int pop_back(void) { //끝 노드의 전 노드 키값 반환 및 노드 삭제
	int i = -1; //덱이 비어있을 경우 그대로 반환하기 위해 -1로 초기화
	if (!empty()) {
		node* t = tail->prev;
		i = t->key;
		t->prev->next = tail;
		tail->prev = t->prev;
		free(t);
	}
	return i;
}

int front(void) { //pop_front와 동일한 로직이지만, 삭제 없이 값만 반환
	int i = -1;
	if (!empty()) i = head->next->key;
	return i;
}

int back(void) { //pop_back과 동일한 로직이지만, 삭제 없이 값만 반환
	int i = -1;
	if (!empty()) i = tail->prev->key;
	return i;
}

int main(void) {

	int n, k;
	scanf("%d", &n);

	init();

	for (int i = 0; i < n; i++) {
		char s[11];
		scanf("%s", s);
		if (strcmp(s, "push_front") == 0) {
			scanf("%d", &k);
			push_front(k);
		}
		else if (strcmp(s, "push_back") == 0) {
			scanf("%d", &k);
			push_back(k);
		}
		else if (strcmp(s, "pop_front") == 0) printf("%d\n",pop_front());
		else if (strcmp(s, "pop_back") == 0) printf("%d\n", pop_back());
		else if (strcmp(s, "size")==0) printf("%d\n", size());
		else if (strcmp(s, "empty")==0) printf("%d\n",empty());
		else if (strcmp(s, "front")==0) printf("%d\n", front());
		else if (strcmp(s, "back")==0) printf("%d\n", back());
	}

	return 0;
}

 

덱의 경우, 스택과 큐와는 달리 앞뒤 양쪽으로 값을 반환할 수 있으므로 

연산 횟수를 줄이기 위해 이중 연결 리스트 형태로 구현하였다. 

큐 문제와 마찬가지로 구현해야 할 기능이 친절하게 설명되어 있으므로

문제에서 요구하는 대로 기능을 함수로 따로 빼주면 끝.

 

(풀어보기 : https://www.acmicpc.net/problem/10866)