[C/C++] C언어 Deque 덱을 이용해 문자열을 입력받아 회문 판별하기

안녕하세요!

 

이번 시간 역시 예전에 공부했던 C언어를 포스팅하려고 합니다.

그중에서 Deque 덱을 이용한 회문 판별 알고리즘인데요.

제가 공부했던 쉽게 풀어쓴 C언어에서 덱을 이용한 알고리즘이 과제로 나왔었는데,

한국어로 된 포스팅이 없어서 덱을 이용한 회문 역시 포스팅하게 되었습니다.

입력된 문자열로 회문을 판별하는 실습을 진행하겠습니다.

 

우선 Deque 덱과 회문이 무엇인지 알아야 하는데요.

 

"덱(Deque)이란?"

덱은 삽입과 삭제가 양쪽 끝에서 모두 가능한 자료 구조 형태입니다.
2개의 포인터를 사용하여 양쪽에 삽입 또는 삭제를 할 수 있는데요.
FIFO 구조의 큐(Queue)와 LIFO 구조의 스택(Stack)을 합친 형태라고 생각하시면 될 것 같습니다.

"회문이란?"

거꾸로 읽어도 제대로 읽는 것과 같은 문장, 낱말, 숫자, 문자열을 가리킵니다.

예를 들어 "level" 같은 단어는 정방향, 역방향 어느 쪽으로 읽어도 같은 "level"이기 때문에 회문입니다.

사실 대부분의 프로그램은 이런 공백 문자를 제거하는 trim 역시 구현되어 있습니다만

이번 시간에는 덱을 이용한 회문으로 코드를 간소화하기 위해 공백 문자 제거 함수는 이전 포스팅을 참고해주세요!

 

먼저 코드를 보겠습니다.

 

C program code

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

struct Node {
	char info;
	struct Node* next;
};

typedef struct Node* nodeptr;

struct Node* getNode()
{
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	return newNode;
}


void freeNode(nodeptr* q)
{
	free(q);
}


void push(nodeptr* q, char x)
{
	nodeptr foo = *q;
	*q = getNode();
	(*q)->info = x;
	(*q)->next = foo;
}



char pop_q(nodeptr* q)

{
	nodeptr foo = *q;
	char val = 0;
	if (foo == NULL)
	{
		return val;
	}

	if (foo->next == NULL)
	{
		val = foo->info;
		*q = NULL;
		return val;
	}
	else
	{
		//마지막 노드로 이동 
		while ((foo->next)->next != NULL)
		{
			foo = foo->next;
		}
		val = (foo->next)->info;
		foo->next = NULL;
		free(foo->next);
		return val;
	}
}



char pop_stack(nodeptr* s)

{
	nodeptr foo = *s;
	char val = 0;
	if (foo == NULL)
	{
		return val;
	}

	else
	{
		val = foo->info;
		*s = foo->next;
		return val;
	}
}


int main()

{
	nodeptr Queue;
	nodeptr Stack;

	char str[32];
	char bar, foo;
	int i;
	
	Queue = 0;
	Stack = 0;

	printf("%s\n", "회문을 판별할 단어를 입력하세요:\n");
	scanf("%s", str);

	// 큐와 스택에 삽입 

	i = 0;
	while ((bar = tolower(str[i])) != '\0')
	{
		push(&Queue, bar);
		push(&Stack, bar);
		i++;
	}



	// 팝, 출력문 
	i = 1;
	bar = 1;
	foo = 1;
	while (bar != 0 && foo != 0 && i == 1)
	{
		bar = pop_stack(&Stack);
		foo = pop_q(&Queue);

		if (bar != foo)
			i = 0;
	}


	if (i == 1)
		printf("회문입니다\n");
	else
		printf("회문이 아닙니다\n");

	return 0;

}

우선 코드를 살펴보시면 Node와 pop, push를 이용해서 데이터를 삽입하거나 삭제하기 위해

꺼내는 것을 확인할 수 있습니다.

두번째로 눈에 띄는 것은 main에서 Queue와 Stack을 사용하는 것인데요.

앞서 얘기했다시피 덱(Deque)은 큐(Queue)와 스택(Stack)을 합쳐놓은 것과 기능이 같습니다.

 

문자열을 입력하면 push 함수를 통해 큐와 스택에 동시에 삽입하고,

pop 함수를 통해 앞과 뒤에서 문자열을 하나씩 꺼내어 그 값이 같은지 비교하여

같으면 회문으로 판별하고, 같지 않으면 문자열이 다르기 때문에 회문이 아닌 것으로 판별하게 됩니다.

 

따로 공백 제거 함수를 구현하지 않았기 때문에 공백 제거까지 하고 싶으신 분은 이전 포스팅의

RemoveSpace 함수를 참고해주세요!

 

출력 결과를 확인해보겠습니다.

 

출력 결과

덱(deque)를 이용한 회문 판별

 

C를 공부하면서 회문 예제를 한 번쯤 보실 수 있는데,

여러 가지 자료구조에서 회문 알고리즘을 응용하여 사용할 수 있습니다.

 

C 강의 때 처음 회문을 접해보고, 자료구조 시간에 스택, 큐, 덱을 이용한 회문을 실습했던 기억이 있습니다.

공부하면서 덱으로 회문을 구현하는 예제와 C언어를 다루는 예제가 거의 없었던 것 같아요.

이번 실습 역시 2학년 때 자료구조 시간에 과제로 나왔던 기억이 있는데

공부나 과제에 참고하셨으면 합니다!

 

고생하셨습니다!