여러 괄호를 사용하는 VPS 찾기

 아래 포스트에서는 소괄호() 만이 입력으로 들어왔기 때문에 굳이 스택을 만들지 않고 작성해도 되었지만, 만일 대-중-소괄호를 모두 이용한다면 어떻게 해야 할까요? 링크된 포스트의 코드로는 답이 되지 않습니다.

BAEKJOON 9012 : 괄호 for C

# BAEKJOON의 문제를 풀이하기 위한 용도가 아니므로 입력은 한 번만, 그리고 최대 100개의 문자를 받을 수 있도록 제한합니다.

---

스택을 만들자

 만일 여러 종류의 괄호를 이용한다면 스택이 필요합니다. 물론 배열을 스택처럼 만들어 사용해도 되지요. 바로 아래 코드는 이번 포스트에서 사용할 스택을 위한 함수의 집합입니다.

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

typedef struct stack{
	unsigned length;
	unsigned maxLength;
	int* data;
}stack;

stack* CreateStack(){
	stack* temp = (stack*)malloc(sizeof(stack) * 1);
	temp->length = 0;
	temp->maxLength = 10;
	temp->data = (int*)malloc(sizeof(int) * temp->maxLength);
	return temp;
}

int DeleteStack(stack* st){
	if(!st) return -1;
	free(st->data);
	free(st);
}

int push(stack* st, char val){
	if(!st) return -1;
	st->data[st->length++] = val;
}

int top(stack *st){
	return st->data[st->length - 1];
}

int pop(stack* st){
	if(!st) return -1;
	return st->data[--st->length];
}

int isEmpty(stack* st){
	return !st || st->length == 0;
}

int GetStackLength(stack* st){
	return st->length;
}

 

---

 

메인을 구성하자

 메인 함수의 기본 골격 구조는 다음과 같습니다. 100개의 문자를 받기 위해서는 마지막 NULL문자를 포함해야 하므로 배열의 길이는 101로 작성해줍니다.

int main(void){
	stack* st = CreateStack();
	char str[101];

	char arr[128] = {0,}; // 편의를 위한 코드입니다.
	arr[']'] = '[';
	arr[')'] = '(';
	arr['}'] = '{';       // 편의를 위한 코드입니다.
    
	scanf("%s", str);
    
	// 작업이 필요합니다.
	
	DeleteStack(st);
	return 0;
}

 이제 들어온 문자 개수만큼만 반복문을 돌면 됩니다. 이 때 여는 괄호 ( (, {, [ )가 나오면 스택에 해당 괄호 값을 넣어줍니다.

	for(int i =0 ; str[i]; ++i){ // NULL문자는 문자의 값 자체로 0이므로 널문자를 만나면 나갑니다.
		if(str[i] == '[' || str[i] == '(' || str[i] == '{'){
			push(st, str[i]);
		}else{
			// 닫는 괄호를 만났을 때
			
		}
	}

 이제 닫는 괄호를 만났을 때입니다. VPS는 여는 괄호와 닫는 괄호가 개수만 맞아선 되지 않습니다. 여는 괄호에 맞게 닫는 괄호가 알맞게 들어섰는가? 남는 괄호는 없는가? 괄호가 부족하지는 않은가? 등 여러 가지를 판별해야 합니다.

 스택을 사용한 VPS 판별에서 여는 괄호는 스택에 값을 추가하는 과정이고, 닫는 괄호는 스택에 값을 꺼내는 과정입니다. 따라서 꺼내기 전에 꺼낼 값이 없지는 않은지 판단합니다. 다음으로, 값을 꺼냈다면 꺼낸 값이 알맞은 값인지 판단해야 합니다.

			if(isEmpty(st)){
				WrongBracket();
				return -1;
			}
			char temp = pop(st);
			if(arr[str[i]] != temp){
				WrongBracket();
				return -1;
			}

 첫 번째 if문에서 스택이 비어있는지를 판단하고, 두 번째 if문에서 꺼낸 값이 알맞은 값인지 판단합니다.

 WrongBracket()은 여러 번 코드를 작성하기 귀찮아서 만든 잘못된 괄호 표기임을 출력하는 함수입니다.

# 코드 풀어서 보기

 두 번째 if문이 감이 안 오실 수 있습니다. 이건 앞서 편의를 위해 작성한 코드가 들어가 있는 것입니다. 이 코드는 풀어 해석하면 다음과 같이 세 개의 if문으로 분리될 수 있습니다.

if(str[i] == '}' && temp == '{'){

}else if(str[i] == ')' && temp == '('){

}else if(str[i] == ']' && temp == '['){

}

 풀어쓰면 현재 입력으로 받은 문자가 닫는 괄호일 때, 스택에서 꺼낸 값이 입력을 받는 괄호와 알맞게 연관된 것인지 판단하는 과정입니다. 이렇게 조건문을 넣으면 넣을수록 프로그램은 느려집니다. 코드도 난잡해지죠. 그래서 편의성 코드를 위에 추가한 것입니다.

 이렇게 작성하고 나면 반복문 내부는 아래와 같아집니다.

	for(int i =0 ; str[i]; ++i){
		if(str[i] == '[' || str[i] == '(' || str[i] == '{'){
			push(st, str[i]);
		}else{
			if(isEmpty(st)){
				WrongBracket();
				return -1;
			}
			char temp = pop(st);
			if(arr[str[i]] != temp){ // 두 번째 닫는 괄호 처리
				WrongBracket();
				return -1;
			}
			
		}
	}

 여기에서, 우리는 알게 모르게 자동으로 처리한 문제점이 있습니다. 닫는 괄호가 더 많을 때입니다. 닫는 괄호가 더 많다면 스택엔 불러올 값이 존재하지 않으므로 -1을 반환하여 temp 변수에는 -1을 담게 됩니다. 각 괄호의 값은 -1이 아니므로 닫는 괄호가 더 많을 경우에는 두 번째 if문에서 처리가 이루어집니다.

 이제 반복문을 나와서 isEmpty로 조건을 거는 if문을 한 번 더 작성해줍니다.

	if(isEmpty(st)){
		printf("맞은 괄호 표기법입니다.\n");
	}else{
		WrongBracket();
	}

 이렇게 코드를 작성한 이유는 여는 괄호가 더 많을 때를 대비한 것입니다. 만일 여는 괄호로 입력이 종결되었다면 스택엔 하나 이상의 값이 존재할 것이고 이는 VPS가 아님을 의미합니다. 이를 판단하기 위한 코드입니다.

 최종적인 코드는 다음과 같습니다.

# 최종 코드 확인하기

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

typedef struct stack{
	unsigned length;
	unsigned maxLength;
	int* data;
}stack;

stack* CreateStack(){
	stack* temp = (stack*)malloc(sizeof(stack) * 1);
	temp->length = 0;
	temp->maxLength = 10;
	temp->data = (int*)malloc(sizeof(int) * temp->maxLength);
	return temp;
}

int DeleteStack(stack* st){
	if(!st) return -1;
	free(st->data);
	free(st);
}

int push(stack* st, char val){
	if(!st) return -1;
	st->data[st->length++] = val;
}

int top(stack *st){
	return st->data[st->length - 1];
}

int pop(stack* st){
	if(!st) return -1;
	return st->data[--st->length];
}

int isEmpty(stack* st){
	return !st || st->length == 0;
}

int GetStackLength(stack* st){
	return st->length;
}

void WrongBracket(){
	printf("잘못된 괄호 표기법\n");
}

int main(void){
	stack* st = CreateStack();
	char str[100];
	
	char arr[128] = {0,};
	arr[']'] = '[';
	arr[')'] = '(';
	arr['}'] = '{';

	scanf("%s", str);
	for(int i =0 ; str[i]; ++i){
		if(str[i] == '[' || str[i] == '(' || str[i] == '{'){
			push(st, str[i]);
		}else{
			if(isEmpty(st)){
				WrongBracket();
				return -1;
			}
			char temp = pop(st);
			if(arr[str[i]] != temp){
				WrongBracket();
				return -1;
			}
			
		}
	}
	
	if(isEmpty(st)){
		printf("맞은 괄호 표기법입니다.\n");
	}else{
		WrongBracket();
	}
		
	DeleteStack(st);
	return 0;
}

---

읽을거리

 편의를 위한 코드에 대한 추가 글입니다. 메모리를 더 사용함으로써 속도적인 이득을 얻는데 사용하는 문법을 설명합니다.

함수 포인터를 배워야하는 이유

 스택을 이용한 문제 하나를 풀어보았습니다. 관심있다면 함께 풀어보셔도 좋을 것 같습니다.

주가 스팬 계산하기

# index