c언어 27497번 알파벳 블록 (백준)

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

typedef struct Node{  //deque에 들어갈 노드 구현
	char data;
	struct Node* before; //앞에 있는 노드의 주소
	struct Node* next; //뒤에 있는 노드의 주소
}Node;

typedef struct Deq{ //deque 구현
	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, char 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, char 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++;
}

char frontPop(Deq* d) { //앞에서 꺼내기
	if(isEmpty(d)) return '0';
	Node* ptr = d->front;
	char tmp = ptr->data;
	d->front = ptr->next;
	free(ptr);
	d->cnt--;
	return tmp;
}
char backPop(Deq* d) { //뒤에서 꺼내기
	if(isEmpty(d)) return '0';
	Node* ptr = d->rear;
	char tmp = ptr->data;
	d->rear = ptr->before;
	free(ptr);
	d->cnt--;
	return tmp;
}

int main(void) {
	Deq d; //덱 구현
	Deq stack; //덱에서 한쪽만 사용하면, stack이니 deq을 stack처럼 사용 (물론 용량은 낭비된다)
	init(&d);
	init(&stack);
	
	int n;
	scanf("%d", &n);
	
	for(int i = 0; i<n; i++) {
		int tmp;
		char c;
		scanf("%d", &tmp);
		getchar(); //buffer의 '\n'제거
		switch(tmp) {
			case 1:
				scanf(" %c", &c);
				backPush(&d, c); //뒤로 넣고
				printf("hello\n");
				frontPush(&stack, '1'); //들어온 순서를 담을 스택에 넣어준다
				break;
			case 2:
				scanf(" %c", &c);
				frontPush(&d, c); //앞으로 넣고
				frontPush(&stack, '2'); //들어온 순서를 담을 스택에 넣어준다
				break;
			case 3:
				if(frontPop(&stack) == '1') backPop(&d); //가장 최근에 들어온 것을 덱에서 빼낸다.
				else frontPop(&d);
				break;
		}
	}
	
	if(isEmpty(&d)) { //덱이 비었으면
		printf("0"); //0을 출력
		return 0; 
	}
	while(!isEmpty(&d)) printf("%c", frontPop(&d)); //덱이 안비었다면, 앞에서부터 꺼내서 출력
}

풀이 : deque (+ stack)

 

0. c언어의 경우 덱을 구현할 때는, 정적인 배열로 만들거나, 노드를 동적할당하여 가변적으로 만들 수 있습니다.

위의 코드는 공간이 가변적인 덱 입니다.

 

구조체로 노드와, 덱을 만들고,

함수로, 초기화, 앞에 넣기, 뒤에 넣기, 앞에서 꺼내기, 뒤에서 꺼내기를 구현합니다.

노드는 요소를 넣을 때 동적할당을 하고,

요소를 꺼낼때는 동적할당을 해제 하면 됩니다.

 

이 문제에선, 가장 최근에 들어온 것을 꺼낼 수가 있도록 만들어야 하는데, 이런 경우

스택을 이용하여, 어떻게 들어갔는지를 넣어주면, 자연스레 스택에서 꺼낼때 마다, 가장 최근것이 어떻게 들어갔는지를 알 수 있게 됩니다.

 

스택을 구현해도 되나, 덱으로 만든 다음, 한 쪽만 사용해도 기능은 스택과 같습니다.

 

1. 덱과, 함수들을 구현합니다.

2. 문자들을 담을 덱과, 들어온 순서를 담아줄 스택을 덱으로 생성합니다.

3. n입력

4. (1) (2) (3) 중 하나를 입력 받고, (1) (2) 일 경우 덱에다가 넣어준 다음, 어떻게 넣었는지를  스택에 넣습니다.

(3)일 경우 stack에서 가장 최근 것을 꺼낸후, 꺼낸 것을 이용하여, 덱에서 문자 하나를 꺼냅니다.

5. 덱이 비어있다면, 0을 출력하며, 그렇지 않다면, 덱의 앞에서부터 하나씩 꺼낸뒤 출력합니다.

 

(c++이 더욱 빠르고, 편합니다)

 

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

27497번: 알파벳 블록