c언어 5430번 AC (백준)

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

typedef struct Node{ //노드
	int data;
	struct Node* before; //앞
	struct Node* next; //뒤
}Node;

typedef struct Deq{ //덱
	Node* front;
	Node* rear;
	int cnt;
}Deq;

void init(Deq* d) { //초기화
	d->front = d->rear = NULL;
	d->cnt = 0;
}
int isEmpty(Deq* d) {return d->cnt == 0;} //비었는가?

void frontPush(Deq* d, int e) { //앞에 넣기
	Node* node = (Node*) malloc(sizeof(Node));
	node->next = node->before = NULL;
	node->data = e;
	
	if(isEmpty(d)) d->front = d->rear = node;
	else {
		node->next = d->front;
		d->front->before = node;
		d->front = node;
	}
	d->cnt++;
}

void backPush(Deq* d, int e) { //뒤에 넣기
	Node* node = (Node*) malloc(sizeof(Node));
	node->next = node->before = NULL;
	node->data = e;
	
	if(isEmpty(d)) d->front = d->rear = node;
	else {
		node->before = d->rear;
		d->rear->next = node;
		d->rear = node;
	}
	d->cnt++;
}

int frontPop(Deq* d) { //앞에서 빼기
	if(isEmpty(d)) return '0';
	Node* ptr = d->front;
	int tmp = ptr->data;
	d->front = ptr->next;
	free(ptr);
	d->cnt--;
	return tmp;
}

int backPop(Deq* d) { //뒤에서 빼기
	if(isEmpty(d)) return '0';
	Node* ptr = d->rear;
	int tmp = ptr->data;
	d->rear = ptr->before;
	free(ptr);
	d->cnt--;
	return tmp;
}

void sub(void) {
	Deq d; //덱
	Deq q; //덱이지만 큐처럼 사용
	init(&d);
	init(&q);
	
	char s, sw = 0;
	int n;
	while((s=getchar()) != '\n') backPush(&q, s); //명렁어 집어넣기
	scanf("%d", &n); //n입력
	getchar(); //buffer '\n' 제거
	
	n=0;
	while((s=getchar()) != '\n') { //문자열 -> 숫자로 바꿔서 덱에 넣기
		if(s>='0' && s<='9') {
			n*=10;
			n+=s-'0';
			sw=1; //숫자가 나오면
		} else {
			if(sw) { //덱에 집어넣을 수 있습니다
				backPush(&d, n);
				n=0;
				sw=0; //다시 0으로 바꾸어 줍니다.
			}
		}
	}
	
	sw = 1; //이번엔 1일 경우 앞에서 꺼내며, 0이면 뒤에서 꺼냅니다.
	while(!isEmpty(&q)) {
		if(frontPop(&q) == 'R') {
			sw = sw ^ 1; //1은 0으로, 0은 1로 변환
		}
		else {
			if(d.cnt == 0) { //만약 덱에 아무것도 없는데, 뺄려고 하면 error가 뜹니다.
				printf("error\n");
				return;
			}
			if(sw) frontPop(&d);
			else backPop(&d);
		}
	}
	//덱에 있는 숫자들을 출력합니다 [ , ..., ] 이런 모양으로
	printf("[");
	while(!isEmpty(&d)) {
		if(sw) printf("%d", frontPop(&d));
		else printf("%d", backPop(&d));	
		if(!isEmpty(&d)) printf(",");
		else break;
	} printf("]\n");
}

int main(void) {	
	int t;
	scanf("%d", &t); //테스트 케이스
	getchar(); //buffer '\n' 제거하기
	
	while(t--) { 
		sub();
	}
}

풀이 : 덱 (deque)

 

0. 덱을 가변적으로 만듭니다

1. 테스트 케이스를 받습니다.

2. 덱과, 큐를 만듭니다. (물론 덱을 두개 만들어 놓고, 하나는 큐로 사용하다보니, 용량이 낭비가 됩니다)

3. 덱과 큐를 초기화 합니다.

4. 명령어들을 큐에 저장합니다.

5. [ , ... , ] 이런식으로 준 숫자들을 덱에 저장합니다.

6. R을 실행할 경우, 덱에 있는 요소들을 전부 뒤집기엔 시간이 매우 걸리기에,

  처음에는 앞에서 꺼내도록 만들다가, R이 입력되면 뒤에서 꺼내도록 만드는 것으로

 요소를 전부 뒤집는 것을 대체 할 수 있습니다. 처음 값은 앞에서 꺼내는 것 입니다.

7. D을 실행할 경우 앞에서 꺼내거나 또는 뒤에서 꺼냅니다.

 7-1. 만약 덱에 아무것도 없는데, 꺼낼려고 하면 error을 출력한 다음 이번 테스트케이스를 종료합니다.

8. 명렁어가 다 실행되면, 덱에 있는 것들을 하나씩 꺼내서 형식에 맞게 출력합니다.

 

꺼내는 곳을 바꾸는 것은 변수를 통해서 통제 할 수 있습니다.

변수 = 1  일 때 앞에서 꺼내며

변수 = 0 일 때 뒤에서 꺼냅니다.

 

R이 실행되면 변수의 값은 1->0, 0->1 을 합니다 (마치 on-off 스위치 처럼)

 

꺼내는 곳을 반대로 하는 것은, 덱의 모든 요소를 뒤집은 것과 같습니다.

 

https://www.acmicpc.net/problem/5430

5430번: AC