[백준/BOJ] 28279번 덱 2 (C/C++)

백준 온라인 저지(BOJ) 28279번 덱 2
https://www.acmicpc.net/problem/28279

28279번: 덱 2

* 사용언어 : C언어, C++
 

1. 문제

정수를 저장하는 덱을 구현한 후, 입력으로 주어지는 명령을 처리하는 프로그램 구현

 

2. 풀이

Library를 사용하지 않고 DEQUE 자료 구조를 구현해보았습니다.
List 계열 자료구조를 구현할 때 자주 활용하는 방식인데,
연습을 충분히 하면 관련 자료구조를 구조화하는 역량이 많이 늘어납니다.
 
_node를 struct로 구현한 뒤 각 _node의 next, prev를 _node pointer(주소)로 저장하는 방식입니다.
 
메모리를 효율적으로 사용하려면 malloc과 free를 사용하는 것이 맞지만
통상적인 알고리즘 시험에서 사용하기에는 불안정한 느낌이 들기 때문에
_node 배열을 통째로 선언해두고 1개씩 가져와서 사용했습니다.
 
신규 node가 추가될 때는 신규 node의 prev와 next를 먼저 연결해주고
이후에 prev 와 next에서 신규 node를 바라보게 하면 연결 실수를 줄일 수 있습니다.
 
그 외 구조는 단순하니 아래 코드로 설명  대체하겠습니다.
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
28279_덱 2
24552KB	252ms
*/
#include <cstdio>

const int LM = 1000002;

struct _node {
	int v;
	_node* prev;
	_node* next;
} NODE[LM];

int idx, size;
int n, o, x;
_node* head, * tail, * node;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	head = &NODE[idx++];
	tail = &NODE[idx++];
	head->next = tail;
	tail->prev = head;

	scanf("%d", &n);
	while (n--) {
		scanf("%d", &o);
		switch (o) {
		case 1:
			scanf("%d", &x);
			node = &NODE[idx++];
			node->v = x;
			node->next = head->next;
			node->prev = head;
			node->next->prev = node;
			head->next = node;
			++size;
			break;
		case 2:
			scanf("%d", &x);
			node = &NODE[idx++];
			node->v = x;
			node->next = tail;
			node->prev = tail->prev;
			tail->prev->next = node;
			tail->prev = node;
			++size;
			break;
		case 3:
			if (size == 0) printf("-1\n");
			else {
				printf("%d\n", head->next->v);
				head->next->next->prev = head;
				head->next = head->next->next;
				--size;
			}
			break;
		case 4:
			if (size == 0) printf("-1\n");
			else {
				printf("%d\n", tail->prev->v);
				tail->prev->prev->next = tail;
				tail->prev = tail->prev->prev;
				--size;
			}
			break;
		case 5:
			printf("%d\n", size);
			break;
		case 6:
			printf("%d\n", size == 0);
			break;
		case 7:
			if (size == 0) printf("-1\n");
			else printf("%d\n", head->next->v);
			break;
		case 8:
			if (size == 0) printf("-1\n");
			else printf("%d\n", tail->prev->v);
			break;
		}
	}
	return 0;
}