JArchive 프로그래밍 일기

목차

0x00 수식의 괄호 쌍이란?

0x01 문제 해결을 위한 관찰

0x02 문제 해결 방법

0x03 연습문제

0x00 수식의 괄호 쌍이란? 

수식의 괄호 쌍이 짝이 맞는지 확인해보자. 

( 이 있으면 ) 으로 닫아야 짝이 맞다. { 이 있으면 } 이 있어야한다. 

두 번째 식에서 (12+4} 여기가 틀렸다. 이와 같이 수식의 괄호 쌍이란, 주어진 괄호 문자열이 올바른지 판단하는 문제다. 

0x01 문제 해결을 위한 관찰 

아래의 3개 수식 중에 올바른 괄호 쌍은 무엇 무엇이 있을까? 

결론부터 말하면 첫 번째 식만 올바른 괄호 쌍이다. 

판단 방법 중에 가장 보편적인 방법은 바로 안쪽부터 짝 맞추기를 해서 지워나가는 방법이다. 

그리고 관찰력이 뛰어나다면,  ')' 의 개수가 '(' 의 갯수를 넘지 않으면 된다는 사실도 있다. 

괄호의 종류가 () 말고도 {}, [] 이 있다면, 여는 괄호의 갯수와 닫는 괄호의 갯수 비교만으로 해결되지 않는다. 

우리는 머릿속으로 어떤 로직을 거쳐서 판단한 걸까? 생각의 과정을 관찰하여 코드로 구현해보자. 

스택을 이용하여 구현해보자. 

아래의 관찰을 인지해야 한다. 

"닫는 괄호는 남아있는 괄호 중에서
가장 최근에 읽은 여는 괄호와 짝을 지어 없애버리는 명령이다. " 

1. 스택을 하나 두고, 문자열을 읽어 나가다가 여는 괄호를 만나면 모두 스택에 넣는다. 

2. 문자열을 읽어 나가다가 닫는 괄호를 만나면 스택의 top을 확인한다. 

3. 지금 읽은 것이 닫는 괄호이고 스택의 top이 여는괄호라면?  쌍이 올바른 것이다.

4. 따라서 스택의 top인 여는 괄호를 스택에서 지운다. pop() 

올바르지 않은 괄호 쌍 

올바르지 않은 괄호 쌍의 경우, 과정을 살펴보자. 

1. 문자열을 읽다가 만난 여는 괄호 2개는 모두 스택에 넣는다. 

2. 닫는 괄호 ) 를 만나면, 스택의 top을 확인한다. 

현재 스택의 top은 { 이다. 

3. 스택의 top인 {와 닫는괄호 ) 는 짝이 안맞는다. 

올바르지 않은 괄호 쌍의 예시 2가지 

1. 문자열을 끝까지 읽었는데, 스택에 여는 괄호가 남아있다. 

2. 문자열을 끝까지 읽고 스택도 비었는데, 닫는 괄호가 남아있다. 

0x02 문제 해결 방법 

올바른 괄호 쌍 판단을 위해 문제 해결 방법을 정리해본다. 

1. 여는 괄호가 나오면 스택에 추가.

2. 닫는 괄호가 나왔을 경우, 스택의 top이 짝이 맞는 괄호라면 pop 

3. 스택에 괄호가 남아있지 않으면 올바른 괄호 쌍. 

스택이 비었을 때 top을 참조하면 런타임에러!

0x03 연습문제 

수식의 괄호쌍이 코딩테스트에서 무조건 나온다고 할 정도로 중요하진 않지만,

stack을 이용한 문제가 많기 때문에 연습문제를 꼭 풀어보자. 

다음 시간에는 BFS를 배운다. 

공부 자료 출처 : 바킹독 알고리즘 수식의 괄호 쌍

스택과 스택의 노드 

링크드 리스트는 배열과 달리 인덱스로 노드에 접근할 수 없습니다. 

리스트를 쓰면 배열과는 달리 용량에 제한을 두지 않아도 된다는 장점이 있습니다. 

그러나 '인덱스'가 없기 때문에 자신의 위에 위치하는 노드를 가리키는 포인터가 필요합니다. 

( 자신의 위에 위치한다: 스택 구조에서 자기 노드를 기준으로 최상위 노드 방향을 '위'라고 한 것입니다. )

typedef struct Node {
	char* data;
	struct Node* nextNode;
}Node;

스택의 구조체입니다. 

배열과는 다르게 최대길이, 최상위 노드의 인덱스가 필요 없습니다. 

그 대신 리스트의 헤드와 테일을 가리키는 포인터가 필요합니다. 

스택의 구조체에서 

헤드는 리스트의 '시작점'을 뜻하고, 테일은 '최상위 노드'를 가리킵니다. 

typedef struct LLStack {
	Node* list;
	Node* top;
}LLStack;

스택생성

먼저, 스택을 자유저장소(==스택메모리)에 생성하는 CreateStack() 함수를 만듭니다. 

void CreateStack(LLStack** stack) {

	(*stack) = (LLStack*)malloc(sizeof(LLStack));
	(*stack)->list = NULL;
	(*stack)->top = NULL;

}

노드 생성 

노드 만큼의 메모리를 할당 합니다. 

문자열의 길이와 NULL문자에 필요한 1을  포함한 길이의 메모리를 할당받습니다. 

그곳을 newNode의 data가 가리키도록 합니다. 

자유저장소에 문자열을 저장해야 하므로, strcpy()를 이용하여 저장합니다. 

strcpy() 와 strlen() 함수를 쓰려면 #include <string.h> 선언이 필요합니다.  

Node* CreateNode(char* data) {

	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = (char*)malloc(strlen(data) + 1);
	strcpy(newNode->data, data);
	newNode->nextNode = NULL;

	return newNode;
}

노드를 메모리에서 해제 

문자열을 가리키는 포인터를 메모리에서 해제 후, 노드를 메모리에서 해제합니다. 

void FreeNode(Node* targetNode) {
	free(targetNode->data);
	free(targetNode);
}

스택을 메모리에서 해제 

스택 제거에 앞서 노드들을 메모리에서 전부 해제합니다.

마지막으로 스택을 메모리 해제 합니다. 

// 스택의 메모리해제 
void FreeStack(LLStack* targetStack) {

	while (!IsEmpty(targetStack)) {
		Node* popped = Pop(targetStack);
		FreeNode(popped);
	}

	free(targetStack);
}

Push 연산 

스택이 비었다면 새 노드가 헤드노드가 됩니다. 

그렇지 않다면, 테일 노드를 찾아서 그 뒤에 새 노드를 붙입니다. 

/* Push */
void Push(LLStack* stack, Node* newNode) {
	printf("[ Push ] %s 삽입 \n", newNode->data);

	if (NULL == stack->list) { // 스택이 비었다면, 뉴노드가 헤드.
		stack->list = newNode;
	}
	else {
		// 테일 노드를 찾아서, 그 뒤에 뉴 노드를 붙인다.

		Node* tempNode = stack->list;

		while (NULL != tempNode->nextNode) {
			tempNode = tempNode->nextNode;
		}

		tempNode->nextNode = newNode;
	}

	stack->top = newNode;
}

 다음과 같이 'top' 뒤에 새노르를 추가해도 됩니다. 

void Push(LLStack* stack, Node* newNode) {

	if (stack->top == NULL) {
		stack->list = newNode;
	}
	else {  // 테일 뒤에 붙인다 
		stack->top->nextNode = newNode;
	}

	stack->top = newNode;
}

Pop 연산

Pop 연산은 두 가지 경우를 처리합니다.  

헤드가 탑인 경우 (스택에 노드가 하나 밖에 없다)

탑 직전 노드를 찾아야 하는 경우 (탑 직전 노드를 탑 노드로 갱신해준다)

Node* Pop(LLStack* stack) {

	Node* topNode = stack->top;
	   
	Node* current = stack->list;

	if (current == topNode) { // 헤드가 탑이라면, 1개 남은 노드를 제거하는 상황.
		stack->top = NULL;
		stack->list = NULL;
	}
	else { 	// top의 직전 노드를 찾는다

		while (current->nextNode != stack->top) {
			current = current->nextNode;
		}

		current->nextNode = NULL;
		stack->top = current;		//top 갱신
	}
	
	return topNode;
}

스택이 비어있는지 확인 

int IsEmpty(LLStack* stack) {
	return (NULL == stack->list);
}

스택에 노드가 몇개 있는지 확인 

int GetSize(LLStack* stack) {
	
	Node* temp = stack->list;
	int count = 0;

	while (temp != NULL) {

		temp = temp->nextNode;
		count++;

	}

	return count;
}