백준(baekjoon) [C] - 2504번: 괄호의 값

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

2504번: 괄호의 값

---

#include <stdio.h>  // 괄호의 값
#include <stdlib.h>
#include <string.h>

// 스택에 문자를 저장하는 것이아닌 숫자로 저장
#define round -1
#define angled -2

typedef struct
{
	int ptr;
	int*stk;
}STACK;

int is_empty(STACK* s)
{
	if (s->ptr <= 0)
		return 1;
	else
		return 0;
}

void push(STACK* s, int data)
{
	s->stk[(s->ptr)++] = data;
}

int pop(STACK* s)
{
	if (is_empty(s))
	{
		return 0;
	}
	else
	{
		return s->stk[--(s->ptr)];
	}
}

int top(STACK* s)
{
	int temp = s->ptr;
	return s->stk[--temp];
}

int corret(STACK* s, char* str, int len)
{
	for (int i = 0; i < len; i++)
	{
		if (str[i] == '(')
		{
			push(s, round);
		}
		else if (str[i] == '[')
		{
			push(s, angled);
		}
		else if (!is_empty(s))
		{
			int temp = top(s);
			if (str[i] == ')' && temp == round)
			{
				pop(s);
			}
			else if (str[i] == ']' && temp == angled)
			{
				pop(s);
			}
			else
				return 0;
		}
		else
		{
			return 0;
		}
	}
	if (is_empty(s))
		return 1;
	else
		return 0;
}

int calculate(STACK* s, char* str, int len)
{
	int sum, temp;
	for (int i = 0; i < len; i++)
	{
		sum = 0;
		if (str[i] == '(')
		{
			push(s, round);
		}
		else if (str[i] == '[')
		{
			push(s, angled);
		}
		else if (str[i] == ')')
		{
			while ((temp = pop(s)) != round)
			{
				sum += temp;
			}
			if (sum == 0)
			{
				push(s, 2);
			}
			else
			{
				push(s, sum * 2);
			}
		}
		else if (str[i] == ']')
		{
			while ((temp = pop(s)) != angled)
			{
				sum += temp;
			}
			if (sum == 0)
			{
				push(s, 3);
			}
			else
			{
				push(s, sum * 3);
			}
		}
	}
	sum = 0;
	while (!is_empty(s))
	{
		sum += pop(s);
	}
	return sum;
}


int main()
{
	char str[31];
	scanf("%s", str);
	int len = strlen(str);

	STACK s;
	s.ptr = 0;
	s.stk = malloc(sizeof(int) * len);
	
	if (corret(&s, str, len) == 0)
	{
		printf("%d", 0);
	}
	else
	{
		printf("%d", calculate(&s, str, len));
	}

	
	return 0;
}

---

MEMO

-- 처음에 main 함수에 코드를 모두 작성했는데 89% 시간초과 발생

-- 시간초과 원인을 알지 못하여 구글링을 통하여 함수를 작성하여 해결

-- 매크로를 통해서 스택에 문자를 넣는 것이 아니라 정수형을 넣어서 또 다른 스택 배열(문자 스택, 정수 스택)을 만들 필요 x

 

!! 항상 시간과 공간을 고려하기 !!